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