[LeetCode] 477. Total Hamming Distance 全部汉明距离
The Hamming distance between two integers is the number of positions at which the corresponding bits are different.
Now your job is to find the total Hamming distance between all pairs of the given numbers.
Example:
Input: 4, 14, 2 Output: 6 Explanation: In binary representation, the 4 is 0100, 14 is 1110, and 2 is 0010 (just showing the four bits relevant in this case). So the answer will be: HammingDistance(4, 14) + HammingDistance(4, 2) + HammingDistance(14, 2) = 2 + 2 + 2 = 6.
Note:
- Elements of the given array are in the range of
0
to10^9
- Length of the array will not exceed
10^4
.
这道题是之前那道 Hamming Distance 的拓展,由于有之前那道题的经验,我们知道需要用异或来求每个位上的情况,那么需要来找出某种规律来,比如看下面这个例子,4,14,2 和1:
4: 0 1 0 0
14: 1 1 1 0
2: 0 0 1 0
1: 0 0 0 1
先看最后一列,有三个0和一个1,那么它们之间相互的汉明距离就是3,即1和其他三个0分别的距离累加,然后在看第三列,累加汉明距离为4,因为每个1都会跟两个0产生两个汉明距离,同理第二列也是4,第一列是3。仔细观察累计汉明距离和0跟1的个数,可以发现其实就是0的个数乘以1的个数,发现了这个重要的规律,那么整道题就迎刃而解了,只要统计出每一位的1的个数即可,参见代码如下:
class Solution { public: int totalHammingDistance(vector<int>& nums) { int res = 0, n = nums.size(); for (int i = 0; i < 32; ++i) { int cnt = 0; for (int num : nums) { if (num & (1 << i)) ++cnt; } res += cnt * (n - cnt); } return res; } };
Github 同步地址:
https://github.com/grandyang/leetcode/issues/477
类似题目:
参考资料:
https://leetcode.com/problems/total-hamming-distance/
https://leetcode.com/problems/total-hamming-distance/discuss/96226/Java-O(n)-time-O(1)-Space
相关文章
- Java实现 LeetCode 803 打砖块 (DFS)
- Java实现 LeetCode 789 逃脱阻碍者(曼哈顿距离)
- Java实现 LeetCode 783 二叉搜索树节点最小距离(遍历)
- Java实现 LeetCode 783 二叉搜索树节点最小距离(遍历)
- Java实现 LeetCode 673 最长递增子序列的个数(递推)
- Java实现 LeetCode 477 汉明距离总和
- Java实现 LeetCode 477 汉明距离总和
- Java实现 LeetCode 402 移掉K位数字
- Java实现 LeetCode 72 编辑距离
- Java实现 LeetCode 69 x的平方根
- LeetCode(72):编辑距离
- LeetCode-796. 旋转字符串【字符串匹配】
- 72. 编辑距离——【Leetcode每日一题】
- Leetcode 1184. 公交站间的距离
- Leetcode 1385. 两个数组间的距离值
- Leetcode 1390. 四因数(牛逼,做出来了)
- [LeetCode] 72. 编辑距离 ☆☆☆☆☆(动态规划)
- leetcode 669. Trim a Binary Search Tree
- 【Leetcode刷题Python】 LeetCode 2038. 如果相邻两个颜色均相同则删除当前颜色
- LeetCode 1653. 使字符串平衡的最少删除次数
- 【LeetCode】124.二叉树中的最大路径和