アルゴリズム練習ノート(十七)——漢明距離の計算

ハミング距離とは、2つの数字がバイナリの場合、互いに変換するには数桁の変換が必要であることを意味します.
タイトルアドレス:https://leetcode.com/problems/total-hamming-distance/#/description
タイトル:Total Hamming Distance
説明:
The Hamming distance between two integers is the number of positions at which the corresponding bits are different.
Now your job is to find the total Hamming distance between all pairs of the given numbers.
Example:

Input: 4, 14, 2

Output: 6

Explanation: In binary representation, the 4 is 0100, 14 is 1110, and 2 is 0010 (just
showing the four bits relevant in this case). So the answer will be:
HammingDistance(4, 14) + HammingDistance(4, 2) + HammingDistance(14, 2) = 2 + 2 + 2 = 6.

Note:

Elements of the given array are in the range of  0  to  10^9

Length of the array will not exceed  10^4 .

回答:
1.ハッシュを用いて各数のバイナリを換算してビットとビット間の計算を行う

class Solution {
public:
    unordered_map >map;
    int totalHammingDistance(vector& nums) {
        int size = nums.size();
        for(int i = 0; i < size; i ++){
            int key = nums[i];
            if(key == 0)map[key].push_back(0);
            if(map[key].size() > 0)continue;
            while(key != 0){
                int s = key % 2;
                map[nums[i]].push_back(s);
                key = key/2;
            }
        }
        int count = 0;
        for(int i = 0; i < size; i ++)
            for(int j = i + 1; j < size; j ++){
                count += dis(nums[i], nums[j]);
            }
        return count;
    }
    int dis(int a, int b){
        if(a == b) return 0;
        int count = 0;
        int sa = map[a].size();
        int sb = map[b].size();
        int key = max(sa, sb);
        for(int i = 0; i < key; i ++){
            if(!map[a][i] && map[b][i])
                if(map[b][i] == 1)count ++;
            if(map[a][i] && !map[b][i])
                if(map[a][i] == 1)count ++;
            if(map[a][i] && map[b][i])
                if(map[a][i] != map[b][i])count ++;
        }
        return count;
        
    }
};

2.数字ごとに、1桁ずつのバイナリパスを行い、1桁の数と0の数を得て、互いに変換するオーバーヘッドを算出し、重ね合わせる

class Solution {
public:
    int totalHammingDistance(vector& nums) {
        int size = nums.size();
        if(size < 2) return 0;
        int ans = 0;
        int *zeroOne = new int[2];
        while(true)
        {
            int zeroCount = 0;
            zeroOne[0] = 0;
            zeroOne[1] = 0;
            for(int i = 0; i < nums.size(); i++)
            {
                if(nums[i] == 0) zeroCount++;
                zeroOne[nums[i] % 2]++;
                nums[i] = nums[i] >> 1;
            }
            ans += zeroOne[0] * zeroOne[1];
            if(zeroCount == nums.size()) return ans;
        }
    }
};