【LeetCode】477。総ハミング距離問題解決レポート（Python）
Leetcode 477 Total Hamming Distance Problem Solving Report
タグ：LeetCode
件名アドレス： https://leetcode.com/problems/total-hamming-distance/description/
タイトル説明：
2つの整数間のハミング距離は、対応するビットが異なる位置の数です。
今、あなたの仕事は、与えられた数のすべてのペア間の合計ハミング距離を見つけることです。
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. 注意：
- 指定された配列の要素は0〜10 ^ 9の範囲です
- 配列の長さは10 ^ 4を超えません。
トピック
配列内のすべての数値間のハミング距離を計算します。
問題解決方法
ハミング距離はXOR演算で計算できます。
アレイの長さは10 ^ 4に達し、ブルートフォースソリューションは望ましくありません。
アイデア：配列内の各数値の各2進数の1の数と0の数を計算し、2つの乗算は合計の異なる数になります。
配列内の2つの数値の比較を、32ビットの2進数の比較に巧妙に変更します。時間計算量はO（n）です。
参照： http://www.cnblogs.com/grandyang/p/6208062.html
パターンを見つける：
4: 0 1 0 0 14: 1 1 1 0 2: 0 0 1 0 1: 0 0 0 1最初に最後の列を見てみましょう。3つの0と1つの1があり、それらの間の相互ハミング距離は3、つまり1と他の3つの0の間の累積距離です。次に、3番目の列である累積を見てください。ハミング距離は4です。これは、各1が2つの0を持つ2つのハミング距離を生成するためです。同様に、2番目の列は4、最初の列は3です。累積ハミング距離と0と1の数を注意深く観察すると、実際には0の数に1の数を掛けたものであることがわかります。重要なルールが発見されれば、問題全体が簡単に解決されます。 1桁に1の数で十分です。
コード：
class Solution(object): def totalHammingDistance(self, nums): ''' :type nums: List[int] :rtype: int ''' res = 0 for pos in range(32): bitCount = 0 for i in range(len(nums)): bitCount += (nums[i] >> pos) & 1 res += bitCount * (len(nums) - bitCount) return res日付
2018年3月9日