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

쌍별 조합의 수를 철저하게 열거하고 해밍 거리를 누적하는 것이 가장 간단하고 간단한 솔루션입니다.

결과적으로 데이터 양이 많고 계승 개수가 너무 많으면 타임아웃이 발생하는 것입니다.

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

문제 해결 아이디어 2 - 수직 계산

우리는 종종 다음과 같은 문제를 분석합니다: 가장 간단한 경우 -> 일반적이고 복잡한 경우. 이전에는 가능한 모든 쌍별 조합을 탐색했습니다.

이제 다른 각도에서 살펴보겠습니다. int가 1비트만 갖는다면 -> int는 32비트입니다.

먼저 int가 1비트만 가지고 있는 경우, 즉 배열 nums의 요소는 0 또는 1의 두 가지 상황만 가지게 됩니다. 이때 Hamming distance의 합을 구하는 단계는 다음과 같습니다.

먼저 배열을 두 그룹으로 나눕니다. 한 그룹은 모두 0 비트입니다. 모든 1 숫자는 두 그룹으로 결합됩니다. 하나는 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번 N)$, 즉 $O(N)$입니다.

다음 예를 볼 수 있습니다.

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

먼저 마지막 열을 보면 3개의 0과 1개의 1이 있고, 그 사이의 해밍 거리는 3입니다. 즉, 1과 나머지 3개의 0 사이의 거리는 다음과 같습니다. 세 번째 열에서 누적 해밍 거리는 4입니다. 왜냐하면 각 1은 두 개의 0이 있는 두 개의 해밍 거리를 생성하기 때문입니다. 마찬가지로 두 번째 열도 4이고 첫 번째 열은 3입니다. 각 열의 쌍별 조합에 대한 해밍 거리의 합은 각 열의 0 개수와 1 개수의 합입니다. 각 열의 해밍 거리의 합을 더하면 해당 열의 두 요소 사이의 거리가 됩니다. 질문에 필요한 배열 숫자입니다. 해밍 거리의 합계입니다.

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

추천 학습:

위 내용은 PHP에서 해밍 거리의 합을 계산하는 방법의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!