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). 但此解法相對解法一更快一些.