兩個(gè)整數(shù)的漢明距離指的是這兩個(gè)數(shù)字的二進(jìn)制數(shù)對(duì)應(yīng)位不同的數(shù)量。

計(jì)算一個(gè)數(shù)組中，任意兩個(gè)數(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ù)組的長(zhǎng)度不超過(guò) 10^4。

解題思路

窮舉兩兩組合的數(shù)量，然后累加漢明距離，這個(gè)是最簡(jiǎn)單直白的方案。

結(jié)果是大量數(shù)據(jù)的時(shí)候會(huì)超時(shí)，階乘的數(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ò)展

咱們常常會(huì)這樣分析問(wèn)題：最簡(jiǎn)單的狀況 -> 通常的、復(fù)雜的狀況。以前咱們是：遍歷全部可能的兩兩組合。

如今咱們換一個(gè)角度看：若是int只有1位-> int有32位。leetcode

首先，若是 int 只有 1 位，即數(shù)組 nums 中的元素只有兩種狀況，0 或者 1，此時(shí)求漢明距離總和的步驟以下：get

首先將數(shù)組分紅兩組，全 0 位一組，全 1 位一組

將兩組數(shù)兩兩組合，記一個(gè)為a，一個(gè)為b

若是 a、b 均來(lái)自 0 那一組，或者均來(lái)自 1 那一組，此時(shí)不會(huì)有漢明距離產(chǎn)生。可是若是 a、b 一個(gè)來(lái)自 0 那一組，另一個(gè)來(lái)自1那一組，這時(shí)將會(huì)產(chǎn)生漢明距離

假設(shè) nums 數(shù)組元素個(gè)數(shù)為 n，其中 0 元素個(gè)數(shù)為 k，則 1 元素的個(gè)數(shù)為 n-k，則上一步可以產(chǎn)生漢明距離的總和就是k*(n-k)

k*(n-k) 就是 int 只有 1 位的狀況下的漢明距離總和

若是將 int 的位數(shù)從 1 位擴(kuò)展到 32 位，那么就是將遍歷每一位，而后求出在這一位上的漢明距離和，累加到一塊兒，這樣能夠?qū)⑺惴◤?fù)雜度從 $O(N^2)$ 下降到 $O(32times N)$，即為 $O(N)$。

能夠看下面這個(gè)例子：

十進(jìn)制 二進(jìn)制

4: 0 1 0 0

14: 1 1 1 0

2: 0 0 1 0

1: 0 0 0 1

先看最后一列，有三個(gè) 0 和一個(gè) 1，那么它們之間相互的漢明距離就是 3，即 1 和其余三個(gè) 0 分別的距離累加，而后在看第三列，累加漢明距離為 4，由于每一個(gè) 1 都會(huì)跟兩個(gè) 0 產(chǎn)生兩個(gè)漢明距離，同理第二列也是 4，第一列是 3。各列相互之間兩兩組合的漢明距離總和就是各列 0 的個(gè)數(shù)與 1 的個(gè)數(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計(jì)算漢明距離總和的實(shí)例講解的文章就介紹到這了,更多相關(guān)php計(jì)算漢明距離總和的方法內(nèi)容請(qǐng)搜索好吧啦網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持好吧啦網(wǎng)！