LeetCode 461 Hamming Distance
LeetCode 461 Hamming Distance
一份执着✘
发布于 2019-12-29 20:15:14
发布于 2019-12-29 20:15:14
汉明距离
题意
两个整数之间的汉明距离指的是这两个数字对应二进制位不同的位置的数目。
给出两个整数 x 和 y，计算它们之间的汉明距离。
注意： 0 ≤ x, y < 231.
示例:
输入: x = 1, y = 4
输出: 2
解释:
1 (0 0 0 1)
4 (0 1 0 0)
↑ ↑解法一
解法一可是基于 LeetCode 191 Number of 1 Bits 中的解法二.
class Solution {
public int hammingDistance(int x, int y) {
int res = 0;
for (int i = 0; i < 32; i++) {
if ((x & 1) != (y & 1)) {
res++;
}
x >>= 1;
y >>= 1;
}
return res;
}
}时间复杂度 O(1), 空间复杂度 O(1).
0010 1000
解法二
解法二可是基于 LeetCode 191 Number of 1 Bits 中的解法二.
这里使用到了异或, 他的运算逻辑为参与运算的两个二进制位同号, 则结果为 0, 异号则为 1， 即 0 ∧ 0 ＝ 0, 0 ∧ 1 ＝ 1, 1 ^ 0 = 1, 1 ∧ 1 ＝ 0.
这个规则很符合我们这道题, 两个数异或的结果的二进制位中, 1 的数量就是本题的解.
class Solution {
public int hammingDistance(int x, int y) {
int res = 0;
int z = x ^ y;
while (z != 0) {
z = z & (z - 1);
res++;
}
return res;
}
}时间复杂度 O(1), 空间复杂度 O(1). 但此解法相对解法一更快一些.
本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2019-07-15，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录