LeetCode 排列組合 題目匯總
LeetCode 數(shù)字 題目匯總
LeetCode 動態(tài)規(guī)劃 題目分類匯總
干貨！LeetCode 題解匯總
題目描述
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.
題目分析
此題和第 461 題很像纯丸，初看是 461 題目的延伸。按照那道題的思路來做就是：
- 對數(shù)組中所有的數(shù)進(jìn)行兩兩組合
- 對于每兩個數(shù)的組合敏储，求一次 Hamming Distance
但是這樣做會超時，是因為兩兩組合的時間復(fù)雜度是 O(n^2)朋鞍，而求一次組合也需要最多 32 次循環(huán)已添。
那么應(yīng)該怎么做這道題目呢？題目中的 Explanation 其實是一種誤導(dǎo)番舆，我們真的有必要兩兩組合分別求 Hamming Distance 嗎酝碳？其實是沒有必要的，一次循環(huán)能否取得所有的 Hamming Distance恨狈？
通過分析得出疏哗，Hamming Distance 其實就是每一位的異同。那么這道題目就可以轉(zhuǎn)化為：求x個數(shù)每兩個數(shù)的組合中禾怠，每一位的異同數(shù)量返奉。想到這里，就會發(fā)現(xiàn)其實x個數(shù)中每個數(shù)的數(shù)值并不重要吗氏，重要的是每一位有多少個0和多少個1芽偏。
假設(shè)有x個數(shù)中，第一位有m個0弦讽，n個1污尉，則該位的Hamming Distance 是：m * n。
代碼
public int totalHammingDistance(int[] nums) {
if (nums == null || nums.length < 2) {
return 0;
}
int[] m = new int[31];// 存儲對應(yīng)位數(shù)往产，有多少個0
for(int num : nums) {
for(int i = 0; i < 31; i++) {
if ((num & (1 << i)) == 0) {
m[i]++;
}
}
}
int result = 0;
for(int i = 0; i < 31; i++) {
result += m[i] * (nums.length - m[i]);
}
return result;
}
