PHP에서 해밍 거리의 합을 계산하는 방법
- 醉折花枝作酒筹앞으로
- 2021-07-08 15:52:131884검색
두 정수의 해밍 거리는 두 숫자의 서로 다른 이진수 비트 수를 나타냅니다. 오늘은 편집자가 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에서 해밍 거리의 합을 계산하는 방법의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!