兩個整數(shù)的漢明距離指的是這兩個數(shù)字的二進(jìn)制數(shù)對應(yīng)位不同的數(shù)量。
計算一個數(shù)組中,任意兩個數(shù)之間漢明距離的總和。
實(shí)例
輸入: 4, 14, 2
輸出: 6
解釋:在二進(jìn)制表示中,4表示為0100,14表示為1110,2表示為0010。(這樣表示是為了體現(xiàn)后四位之間關(guān)系)
所以答案為:HammingDistance(4, 14) + HammingDistance(4, 2) + HammingDistance(14, 2) = 2 + 2 + 2 = 6.
注意:
數(shù)組中元素的范圍為從 0到 10^9。數(shù)組的長度不超過 10^4。
解題思路
窮舉兩兩組合的數(shù)量,然后累加漢明距離,這個是最簡單直白的方案。
結(jié)果是大量數(shù)據(jù)的時候會超時,階乘的數(shù)量太多。
class Solution {
/**
* @param Integer[] $nums
* @return Integer
*/
function totalHammingDistance($nums) {
$count = count($nums);
$sum = 0;
for ($i = 0; $i $count - 1; $i++) {
for ($j = $i+1; $j $count; $j++)
{
$sum += $this->hm($nums[$i], $nums[$j]);
}
}
return $sum;
}
// 漢明距離方法
function hm($x, $y)
{
return substr_count(decbin($x ^ $y), '1');
}}
思路擴(kuò)展:
解題思路擴(kuò)展
咱們常常會這樣分析問題:最簡單的狀況 -> 通常的、復(fù)雜的狀況。以前咱們是:遍歷全部可能的兩兩組合。
如今咱們換一個角度看:若是int只有1位-> int有32位。leetcode
首先,若是 int 只有 1 位,即數(shù)組 nums 中的元素只有兩種狀況,0 或者 1,此時求漢明距離總和的步驟以下:get
首先將數(shù)組分紅兩組,全 0 位一組,全 1 位一組
將兩組數(shù)兩兩組合,記一個為a,一個為b
若是 a、b 均來自 0 那一組,或者均來自 1 那一組,此時不會有漢明距離產(chǎn)生??墒侨羰?a、b 一個來自 0 那一組,另一個來自1那一組,這時將會產(chǎn)生漢明距離
假設(shè) nums 數(shù)組元素個數(shù)為 n,其中 0 元素個數(shù)為 k,則 1 元素的個數(shù)為 n-k,則上一步可以產(chǎn)生漢明距離的總和就是k*(n-k)
k*(n-k) 就是 int 只有 1 位的狀況下的漢明距離總和
若是將 int 的位數(shù)從 1 位擴(kuò)展到 32 位,那么就是將遍歷每一位,而后求出在這一位上的漢明距離和,累加到一塊兒,這樣能夠?qū)⑺惴◤?fù)雜度從 $O(N^2)$ 下降到 $O(32\\times N)$,即為 $O(N)$。
能夠看下面這個例子:
十進(jìn)制 二進(jìn)制
4: 0 1 0 0
14: 1 1 1 0
2: 0 0 1 0
1: 0 0 0 1
先看最后一列,有三個 0 和一個 1,那么它們之間相互的漢明距離就是 3,即 1 和其余三個 0 分別的距離累加,而后在看第三列,累加漢明距離為 4,由于每一個 1 都會跟兩個 0 產(chǎn)生兩個漢明距離,同理第二列也是 4,第一列是 3。各列相互之間兩兩組合的漢明距離總和就是各列 0 的個數(shù)與 1 的個數(shù)之和,把各列漢明距離總和再累加就是題目所求的數(shù)組 nums 元素兩兩之間的漢明距離總和。
代碼
class Solution {
/**
* @param Integer[] $nums
* @return Integer
*/
function totalHammingDistance($nums) {
$count = count($nums);
$sum = 0;
for($i = 0; $i 32; $i++)
{
$tmpCount = 0;
for($j = 0; $j $count; $j++)
$tmpCount += ($nums[$j] >> $i) 1;
}
$sum += $tmpCount * ($count - $tmpCount);
}
return $sum;
}
}
到此這篇關(guān)于php計算漢明距離總和的實(shí)例講解的文章就介紹到這了,更多相關(guān)php計算漢明距離總和的方法內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家!