PHP如何計算漢明距離總和

兩個整數的漢明距離指的是這兩個數字的二進位數對應位不同的數目。今天小編就來介紹PHP計算漢明距離總和的方法，有需要的可以參考一下。

兩個整數的 漢明距離 指的是這兩個數字的二進位數對應位元不同的數量。

計算一個陣列中，任兩個數之間漢明距離的總和。

範例:

输入: 4, 14, 2
输出: 6
解释: 在二进制表示中，4表示为0100，14表示为1110，2表示为0010。（这样表示是为了体现后四位之间关系）
所以答案为：HammingDistance(4, 14) + HammingDistance(4, 2) + HammingDistance(14, 2) = 2 + 2 + 2 = 6.

注意:

陣列中元素的範圍為從 0到 10^9。數組的長度不超過 10^4。

解題思路 1

窮舉兩兩組合的數量，然後累加漢明距離，這個是最簡單直白的方案。

結果是大量資料的時候會逾時，階乘的數量太多。

程式碼

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), &#39;1&#39;);
    }}

解題思路2 - 豎著計算

我們常常會這樣分析問題：最簡單的情況-> 一般的、複雜的情況。之前我們是：遍歷所有可能的兩兩組合。

現在我們換一個角度來看：如果int只有1位元-> int有32位元。

首先，若 int 只有1 位，即陣列 nums 中的元素只有兩種情況，0 或1，此時求漢明距離總和的步驟如下：

先將陣列分成兩組，全0 位一組，全1 位一組將兩組數兩兩組合，記一個為a，一個為b如果a、b 均來自0 那一組，或者均來自1 那一組，此時不會有漢明距離產生。但如果a、b 一個來自0 那一組，另外一個來自1那一組，這時將會產生漢明距離假設 nums 數組元素個數為 n，其中0 個元素個數為 k，則1 個元素的個數為 n-k，則上一步能夠產生漢明距離的總和就是k*(n-k)k*(n-k) 就是 int 只有1 位元的情況下的漢明距離總和

如果將 int 的位數從1 位擴展到32 位，那麼就是將遍歷每一位，然後求出在這一位上的漢明距離和，累加到一起，這樣可以將演算法複雜度從$O(N^2)$ 降低到$O(32\times N)$，即為$O(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 產生兩個漢明距離，同理第二列也是4，第一列是3。各列彼此之間兩兩組合的漢明距離總和就是各列0 的個數與1 的個數之和，把各列漢明距離總和再累加就是題目所求的數組 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;
    }
}

推薦學習：php影片教學

#

以上是PHP如何計算漢明距離總和的詳細內容。更多資訊請關注PHP中文網其他相關文章！