Comment calculer la somme de la distance de Hamming en PHP

La distance de Hamming de deux nombres entiers fait référence au nombre de bits binaires différents correspondant aux deux nombres. Aujourd'hui, l'éditeur va vous présenter la méthode de calcul de la somme des distances de Hamming en PHP. Vous pouvez vous y référer si vous en avez besoin.

La distance de Hamming de deux entiers fait référence au nombre de bits différents correspondants dans les chiffres binaires de ces deux nombres.

Calculez la somme des distances de Hamming entre deux nombres quelconques dans un tableau.

Exemple :

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

Remarque :

La plage des éléments du tableau est de 0 à 10^9. La longueur du tableau ne peut pas dépasser 10^4.

Idées de résolution de problèmes 1

Énumérez de manière exhaustive le nombre de combinaisons par paires, puis accumulez la distance de Hamming. C'est la solution la plus simple et la plus directe.

Le résultat est qu'il expire lorsqu'il y a une grande quantité de données et que le nombre de factorielles est trop élevé.

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), '1'); }}

Idées de résolution de problèmes 2 - Calcul vertical

Nous analysons souvent des problèmes comme celui-ci : le cas le plus simple -> cas généraux, complexes. Auparavant, nous étions : parcourir toutes les combinaisons possibles par paires.

Maintenant, regardons les choses sous un autre angle : si int n'a que 1 bit -> int a 32 bits.

Tout d'abord, si int n'a que 1 bit, c'est-à-dire que les éléments du tableau nums n'ont que deux situations, 0 ou 1. À ce stade, les étapes pour trouver la somme de la distance de Hamming sont les suivantes :

Divisez d'abord le tableau en deux groupes, un avec tous les bits 0, tous les groupes de 1 bit combinent deux groupes de nombres par paires, l'un est a, l'autre est b. Si a et b appartiennent tous deux au groupe de 0, ou les deux du groupe de 1, il n'y aura pas de distance de Hamming. Mais si l'un des a et b vient du groupe 0 et l'autre du groupe 1, la distance de Hamming sera générée. Supposons que le nombre d'éléments dans le tableau nums est n et que le nombre d'éléments 0 est k. , alors le nombre de 1 éléments Le nombre est n-k, alors la somme des distances de Hamming qui peuvent être générées à l'étape précédente est k*(n-k)k*(n-k), qui est la somme des distances de Hamming lorsque int n'a que 1 digit Si le nombre de chiffres dans int est étendu de 1 chiffre à 32 bits, alors chaque bit sera parcouru, puis la somme des distances de Hamming à ce bit sera calculée et accumulée ensemble. Cela peut réduire la complexité de l'algorithme de $. O(N^2)$ à $O( 32 fois N)$, soit $O(N)$.

Vous pouvez regarder l'exemple suivant :

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

Regardez d'abord la dernière colonne, il y a trois 0 et un 1, puis la distance de Hamming entre eux est de 3, c'est-à-dire que la distance entre 1 et les trois autres 0 est accumulées, puis regardez Dans la troisième colonne, la distance de Hamming cumulée est de 4, car chaque 1 produira deux distances de Hamming avec deux 0 De même, la deuxième colonne est également de 4 et la première colonne est de 3. La somme des distances de Hamming des combinaisons par paires de chaque colonne est la somme du nombre de 0 et du nombre de 1 dans chaque colonne. La somme des distances de Hamming de chaque colonne est la distance entre les deux éléments de la. nombres de tableaux requis par la question.

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

Apprentissage recommandé :

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!