So berechnen Sie die Summe der Hamming-Distanz in PHP

Der Hamming-Abstand zweier Ganzzahlen bezieht sich auf die Anzahl der verschiedenen binären entsprechenden Bits der beiden Zahlen. Heute stellt der Herausgeber die Methode zur Berechnung der Summe der Hamming-Abstände in PHP vor. Sie können bei Bedarf darauf zurückgreifen.

Der Hamming-Abstand zweier Ganzzahlen bezieht sich auf die Anzahl der verschiedenen entsprechenden Bits in den Binärziffern dieser beiden Zahlen.

Berechnen Sie die Summe der Hamming-Abstände zwischen zwei beliebigen Zahlen in einem Array.

Beispiel:

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

Hinweis:

Der Bereich der Elemente im Array liegt zwischen 0 und 10^9. Die Länge des Arrays darf 10^4 nicht überschreiten.

Ideen zur Problemlösung 1

Zählen Sie die Anzahl der paarweisen Kombinationen ausführlich auf und akkumulieren Sie dann die Hamming-Distanz. Dies ist die einfachste und unkomplizierteste Lösung.

Das Ergebnis ist, dass es zu einer Zeitüberschreitung kommt, wenn eine große Datenmenge vorhanden ist und die Anzahl der Fakultäten zu groß ist.

Code

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;);
    }}

Ideen zur Problemlösung 2 – Vertikale Berechnung

Wir analysieren oft Probleme wie diese: der einfachste Fall -> allgemeine und komplexe Fälle. Zuvor waren wir: alle möglichen paarweisen Kombinationen durchlaufen.

Betrachten wir es nun aus einem anderen Blickwinkel: Wenn int nur 1 Bit hat -> hat int 32 Bit.

Wenn int nur 1 Bit hat, haben die Elemente im Array Nums nur zwei Situationen, 0 oder 1. Zu diesem Zeitpunkt sind die Schritte zum Ermitteln der Summe der Hamming-Distanz wie folgt:

Teilen Sie das Array zunächst in zwei Gruppen auf, eine Gruppe mit allen 0-Bits, alle 1-Ziffern werden in zwei Gruppen zusammengefasst, eine ist a, die andere ist b. Wenn a und b beide aus der 0-Gruppe oder beide aus der 1-Gruppe stammen , es wird keine Hamming-Distanz geben. Wenn jedoch eines von a und b aus der 0-Gruppe und das andere aus der 1-Gruppe stammt, wird eine Hamming-Distanz generiert. Nehmen Sie an, dass die Anzahl der Elemente im Nums-Array n und die Anzahl der 0-Elemente k ist , dann beträgt die Anzahl der 1 Elemente n-k, dann beträgt die Summe der Hamming-Abstände, die im vorherigen Schritt generiert werden können, k*(n-k)k*(n-k), was die Summe der Hamming-Abstände ist, wenn int nur 1 hat Wenn die Anzahl der Ziffern in int von 1 Ziffer auf 32 Bits erweitert wird, wird jedes Bit durchlaufen und dann die Summe der Hamming-Abstände an diesem Bit berechnet und akkumuliert. Dies kann die Komplexität des Algorithmus reduzieren O(N^2)$ zu $O( 32 mal N)$, also $O(N)$.

Sie können sich das folgende Beispiel ansehen:

十进制       二进制
4:        0 1 0 0
14:        1 1 1 0
2:        0 0 1 0
1:        0 0 0 1

Schauen Sie sich zuerst die letzte Spalte an, es gibt drei Nullen und eine 1, dann beträgt der Hamming-Abstand zwischen ihnen 3, also der Abstand zwischen 1 und den anderen drei Nullen akkumuliert, und schauen Sie dann nach: In der dritten Spalte beträgt die kumulative Hamming-Distanz 4, da jede 1 zwei Hamming-Distanzen mit zwei Nullen erzeugt. Ebenso ist die zweite Spalte ebenfalls 4 und die erste Spalte 3. Die Summe der Hamming-Abstände der paarweisen Kombinationen jeder Spalte ist die Summe der Anzahl der Nullen und der Anzahl der Einsen in jeder Spalte. Die Summe der Hamming-Abstände jeder Spalte ergibt den Abstand zwischen den beiden Elementen der Array-Nummern, die für die Frage erforderlich sind. Summe der Hamming-Abstände.

Code

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;
    }
}

Empfohlenes Lernen:

php-Video-Tutorial

Das obige ist der detaillierte Inhalt vonSo berechnen Sie die Summe der Hamming-Distanz in PHP. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!