PHP怎么計算漢明距離總和

這篇文章主要介紹“PHP怎么計算漢明距離總和”，在日常操作中，相信很多人在PHP怎么計算漢明距離總和問題上存在疑惑，小編查閱了各式資料，整理出簡單好用的操作方法，希望對大家解答”PHP怎么計算漢明距離總和”的疑惑有所幫助！接下來，請跟著小編一起來學習吧！

目前成都創(chuàng)新互聯(lián)公司已為成百上千的企業(yè)提供了網(wǎng)站建設、域名、網(wǎng)絡空間、網(wǎng)站運營、企業(yè)網(wǎng)站設計、沾益網(wǎng)站維護等服務，公司將堅持客戶導向、應用為本的策略，正道將秉承"和諧、參與、激情"的文化，與客戶和合作伙伴齊心協(xié)力一起成長，共同發(fā)展。

兩個整數(shù)的 漢明距離 指的是這兩個數(shù)字的二進制數(shù)對應位不同的數(shù)量。

計算一個數(shù)組中，任意兩個數(shù)之間漢明距離的總和。

示例:

輸入: 4, 14, 2
輸出: 6
解釋: 在二進制表示中，4表示為0100，14表示為1110，2表示為0010。（這樣表示是為了體現(xiàn)后四位之間關系）
所以答案為：HammingDistance(4, 14) + HammingDistance(4, 2) + HammingDistance(14, 2) = 2 + 2 + 2 = 6.

注意:

數(shù)組中元素的范圍為從 0到 10^9。數(shù)組的長度不超過 10^4。

解題思路 1

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

結果是大量數(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');
    }}

解題思路 2 - 豎著計算

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

現(xiàn)在我們換一個角度看：如果int只有1位-> int有32位。

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

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

如果將 int 的位數(shù)從 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 產(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;
    }
}

到此，關于“PHP怎么計算漢明距離總和”的學習就結束了，希望能夠解決大家的疑惑。理論與實踐的搭配能更好的幫助大家學習，快去試試吧！若想繼續(xù)學習更多相關知識，請繼續(xù)關注創(chuàng)新互聯(lián)網(wǎng)站，小編會繼續(xù)努力為大家?guī)砀鄬嵱玫奈恼拢?/p>

新聞標題：PHP怎么計算漢明距離總和
瀏覽路徑：http://muchs.cn/article4/ihdiie.html

成都網(wǎng)站建設公司_創(chuàng)新互聯(lián)，為您提供域名注冊、微信公眾號、網(wǎng)站排名、用戶體驗、網(wǎng)站制作、定制網(wǎng)站

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉載內(nèi)容為主，如果涉及侵權請盡快告知，我們將會在第一時間刪除。文章觀點不代表本網(wǎng)站立場，如需處理請聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉載，或轉載時需注明來源： 創(chuàng)新互聯(lián)