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 를 초과 하지 않 습 니 다.
문제 풀이 의 사고 방향.
두 그룹의 수 를 끝까지 들 고 한 명 거 리 를 누적 하 는 것 이 가장 간단 하고 직 설 적 인 방안 이다.
결 과 는 대량의 데 이 터 를 사용 할 때 시간 을 초과 하고 단계 의 수량 이 너무 많다 는 것 이다.

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

아이디어 확장:
문제 풀이 사고의 폭 을 넓히다.
우 리 는 항상 이렇게 문 제 를 분석한다.가장 간단 한 상황->통상 적 이 고 복잡 한 상황.예전 에 우 리 는 모든 가능 한 두 조합 을 옮 겨 다 녔 다.
지금 우 리 는 다른 각도 에서 볼 때 int 가 한 명 만 있다 면->int 는 32 명 이다.leetcode
우선,int 가 1 자리 만 있 으 면 배열 nums 의 요 소 는 두 가지 상황 만 있 습 니 다.0 또는 1.이때 한 명 거 리 를 총화 하 는 절차 아래:get
우선 배열 을 두 그룹 으로 나 누 어 0 명 씩 한 팀 씩,한 팀 씩 나 누 어 줍 니 다.
두 조 를 두 조로 나 누 어 하 나 는 a 이 고 하 나 는 b 이다.
만약 에 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\\\times N)$,즉$O(N)$로 낮 출 수 있 습 니 다.
아래 의 이 예 를 볼 수 있다.
10 진 2 진
4: 0 1 0 0
14: 1 1 1 0
2: 0 0 1 0
1: 0 0 0 1
먼저 마지막 열 을 보면 세 개의 0 과 한 개의 1 이 있다.그러면 그들 사이 의 한 명 거 리 는 3 이다.즉,1 과 나머지 세 개의 0 의 거 리 를 누적 한 다음 에 세 번 째 열 을 보면 한 명 거 리 는 4 이다.각 1 은 두 개의 0 과 두 개의 한 명 거 리 를 형성 하기 때문에 같은 이치 로 두 번 째 열 도 4 이 고 첫 번 째 열 은 3 이다.각 열 이 서로 두 조합 을 이 루 는 한 명 거 리 를 합 친 것 은 각 열 0 의 개수 와 1 의 개수 의 합 이다.각 열 한 명 거 리 를 합 친 다음 에 누적 하 는 것 은 바로 문제 가 요구 하 는 배열 nums 요소 두 개의 한 명 거 리 를 합 친 것 이다.
코드

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

phop 컴 퓨 팅 한 명 거리 총화 에 관 한 인 스 턴 스 설명 에 관 한 글 은 여기까지 입 니 다.더 많은 phop 컴 퓨 팅 한 명 거리 총화 방법 내용 은 우리 의 이전 글 을 검색 하거나 아래 의 관련 글 을 계속 조회 하 시기 바 랍 니 다.앞으로 많은 응원 바 랍 니 다!