LeetCode 461 Hamming Distance

• 2019 年 12 月 29 日
• 笔记

汉明距离

题意

两个整数之间的汉明距离指的是这两个数字对应二进制位不同的位置的数目。

给出两个整数 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). 但此解法相对解法一更快一些.