0%

LeetCode 461: Hamming Distance


Difficulty: Easy

Tags: Bit Manipulation


问题描述

给出2个十进制数 x 和 y,求二者的汉明距离。

汉明距离:将2个十进制数转为二进制后,对应位置上数字不同的位数。


解决方案

因为题目中限定了 x 和 y 的大小范围,用一个32位数组 (其实31位就够了) 存放他们的二进制表示。

十进制转二进制考虑一下边界情况即可,用了一个 lgN 的方法。


▷ Time Complexity: O(lgN)

▷ Space Complexity: O(1)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
class Solution {
public:
int hammingDistance(int x, int y) {
int array_x[32];
int array_y[32];
int hamming_distance = 0;

for(int i=0; i<32; i++)
{
array_x[i] = 0;
array_y[i] = 0;
}

// convert x to binary
int x_counter = 31;

if(x == 1) array_x[31] = 1;
else if(x >= 2)
{
while(x/2 != 0)
{
if(x%2 == 1) array_x[x_counter] = 1;

x /= 2;
x_counter--;
}
array_x[x_counter] = 1;
}

// convert y to binary
int y_counter = 31;

if(y == 1) array_y[31] = 1;
else if(y >= 2)
{
while(y/2 != 0)
{
if(y%2 == 1) array_y[y_counter] = 1;

y /= 2;
y_counter--;
}
array_y[y_counter] = 1;
}


for(int i=0; i<32; i++)
{
if(array_x[i] != array_y[i])
hamming_distance++;
}

return hamming_distance;
}
};

回到 Conquer Leetcode