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

문제 해결 아이디어 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에서 해밍 거리의 합을 계산하는 방법의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!