題目描述:給定一個整數陣列 nums,計算所有整數對 (i, j)(i < j)的漢明距離總和。漢明距離是指兩個整數對應二進位表示中,位元值不同的位置數量。
解題思路:逐對計算的暴力法需要 O(n²),但可以改為「按位元分析」,達到 O(32n) = O(n)。
對每一個位元位置(共 32 位),統計陣列中有多少個數在該位的值為 1(記為 ones),則為 0 的個數為 zeros = n - ones。這個位元位置對總漢明距離的貢獻為 ones * zeros,因為每一個 bit=1 的數和每一個 bit=0 的數配對後,該位元的漢明距離貢獻為 1。
將所有 32 個位元位置的貢獻加總,即得到答案。這個方法的關鍵洞察在於:整體問題可以分解為各個位元的獨立子問題,各位元互不影響。
時間複雜度:O(32 × n) = O(n) — 對每個位元位置遍歷一次陣列,共 32 個位元。
空間複雜度:O(1) — 只使用常數額外空間,不計輸入陣列。
Function totalHammingDistance(nums):
n = length of nums
total = 0
For bit from 0 to 31:
ones = 0
For each num in nums:
ones += (num >> bit) AND 1
zeros = n - ones
total += ones * zeros
Return total暴力逐對計算 O(n²):對每對 (i, j),用 __builtin_popcount(nums[i] ^ nums[j]) 計算漢明距離並累加。實作最直觀,但當 n 達到 10⁴ 時需要 5 × 10⁷ 次操作,在時限內勉強通過,不如按位元法穩定。
位元並行化(SIMD 思路):若使用 64 位元整數,可以同時處理每 64 個數的某位元,減少迴圈次數。但 C++ 標準庫中不常見,而且 LeetCode 的輸入規模 n ≤ 10⁴ 已足夠,優化幅度有限。
XOR + popcount 前綴整合:對同一位元收集所有值後用位元運算批次處理。概念相近,但實作複雜度增加,相對按位元逐一統計並無優勢。