배열에서 가장 일반적인 항목 찾기

https://stackoverflow.com/questions/278488

07-07-2019
|

문제

길이가 최대 2인 32비트 부호 없는 정수 배열이 제공됩니다.³², 일부 32비트 부호 없는 정수 N의 경우 배열 항목의 절반 이상이 N과 동일하다는 속성이 있습니다.배열의 각 숫자를 한 번만 보고 최대 2kB의 메모리를 사용하는 N을 찾습니다.

귀하의 솔루션은 결정론적이어야 하며 N을 찾는 것이 보장되어야 합니다.

해결책

각 비트마다 하나의 정수를 유지하고 배열의 각 정수에 대해이 컬렉션을 적절하게 증가시킵니다.

결국, 비트 중 일부는 배열 길이의 절반보다 높은 카운트를 가질 것입니다. 그 비트는 N을 결정합니다. 물론, 수는 N이 발생한 횟수보다 높지만 중요하지 않습니다. 중요한 것은 N의 일부가 아닌 비트입니다. 할 수 없습니다 절반 이상이 발생합니다 (N은 항목의 절반 이상이기 때문에)과 N의 일부인 비트 ~ 해야 하다 절반 이상이 발생합니다 (N이 발생할 때마다 발생하기 때문에 발생하기 때문에).

(현재 코드가 없음 - 순 액세스를 잃을 것입니다. 위의 것이 충분히 분명합니다.)

다른 팁

보이어와 무어의 "선형 시간 대다수 투표 알고리즘" - 대답에서 현재 추측을 유지하기 위해 배열을 내려갑니다.

두 가지 변수만으로는이 작업을 수행 할 수 있습니다.

public uint MostCommon(UInt32[] numberList)
{
    uint suspect = 0;
    int suspicionStrength = -1; 
    foreach (uint number in numberList)
    {
        if (number==suspect)
        {
            suspicionStrength++;
        }
        else
        {
            suspicionStrength--;
        }

        if (suspicionStrength<=0)
        {
            suspect = number;
        }
    }
    return suspect;
}

첫 번째 번호를 용의자 번호로 만들고 목록을 계속 반복하십시오. 숫자가 일치하면 의심 강도를 하나씩 증가시킵니다. 일치하지 않으면 의심의 힘을 하나로 낮추십시오. 의심 강도가 0에 도달하면 현재 번호는 용의자가됩니다. 이것은 할 것입니다 ~ 아니다 가장 일반적인 숫자, 그룹의 50% 이상인 숫자 만 찾기 위해 노력합니다. 수표를 추가하려는 충동에 저항하십시오 suspicionStrength 목록 길이의 절반보다 큽니다. 항상 더 많은 총 비교를 초래합니다.

추신 : 나는이 코드를 테스트하지 않았다 - 당신 자신의 위험으로 사용하십시오.

Jon의 알고리즘에 대한 의사 코드 (메모장 C ++ :-)) :

int lNumbers = (size_of(arrNumbers)/size_of(arrNumbers[0]);

for (int i = 0; i < lNumbers; i++)
  for (int bi = 0; bi < 32; bi++)
    arrBits[i] = arrBits[i] + (arrNumbers[i] & (1 << bi)) == (1 << bi) ? 1 : 0;

int N = 0;

for (int bc = 0; bc < 32; bc++)
  if (arrBits[bc] > lNumbers/2)
    N = N | (1 << bc);

주의할 점은 다음과 같습니다. a0, a1, . . . , an−1 리더가 포함 된 다음 다른 값의 한 쌍의 요소를 제거한 후 나머지 시퀀스는 여전히 동일한 리더를 갖습니다.실제로, 우리가 두 가지 다른 요소를 제거하면 그 중 하나만이 리더가 될 수 있습니다.새로운 시퀀스의 리더는 더 많이 발생합니다 n/2 − 1 = (n−2)/2타임스.결과적으로 그것은 여전히 새로운 시퀀스의 리더입니다. n − 2 강요.

다음은 O(n) 시간 복잡도를 갖는 Python 구현입니다.

def goldenLeader(A):
    n = len(A)
    size = 0
    for k in xrange(n):
        if (size == 0):
            size += 1
            value = A[k]
        else:
            if (value != A[k]):
                size -= 1
            else:
                size += 1
    candidate = -1
    if (size > 0):
        candidate = value
    leader = -1
    count = 0
    for k in xrange(n):
        if (A[k] == candidate):
            count += 1
    if (count > n // 2):
        leader = candidate
    return leader

이것은 스트리밍 알고리즘 (거대한 데이터 스트림이있는) 스트리밍 알고리즘의 표준 문제 이며이 스트림을 한 번 전달 하여이 스트림에서 일부 통계를 계산해야합니다.

분명히 해싱 또는 정렬로 접근 할 수 있지만 잠재적으로 무한한 스트림으로 메모리가 분명히 떨어집니다. 그래서 당신은 여기서 똑똑한 일을해야합니다.

대부분의 요소는 배열 크기의 절반 이상이 발생하는 요소입니다.. 이는 대부분의 요소가 다른 모든 요소보다 더 많이 발생하거나 횟수를 계산하면 대부분의 요소가 나타나고 다른 모든 요소의 수를 빼면 양수를 얻습니다.

따라서 일부 요소의 수를 계산하고 다른 모든 요소의 수를 빼고 숫자 0을 얻는 경우 원래 요소는 다수 요소가 될 수 없습니다. 올바른 알고리즘의 기초 인 경우 :

카운터와 가능한 요소의 두 가지 변수가 있습니다. 카운터가 0 인 경우 스트림을 반복하십시오 - 가능한 요소를 덮어 쓰고 카운터를 초기화하십시오. 숫자가 가능한 요소와 동일하다면 카운터를 늘리십시오. 그렇지 않으면 감소하십시오. 파이썬 코드 :

def majority_element(arr):
    counter, possible_element = 0, None
    for i in arr:
        if counter == 0:
            possible_element, counter = i, 1
        elif i == possible_element:
            counter += 1
        else:
            counter -= 1

    return possible_element

알고리즘이 있음을 알 수 있습니다 O(n) 전에는 매우 작은 상수가 있습니다 O(n) (같은). 또한 공간 복잡성처럼 보입니다 O(1), 우리는 3 개의 변수 만 초기화 되었기 때문에. 문제는 이러한 변수 중 하나가 잠재적으로 자랄 수있는 카운터라는 것입니다. n (배열이 동일한 숫자로 구성된 경우). 그리고 번호를 저장합니다 n 당신은 필요합니다 O(log (n)) 우주. 그래서 이론적 관점에서 그것은이다 O(n) 시간과 O(log(n)) 우주. 실용적, 당신은 longint에 2^128 번호를 맞출 수 있으며 배열 의이 요소는 상상할 수 없을 정도로 거대합니다.

또한 알고리즘은 다수의 요소가있는 경우에만 작동합니다. 그러한 요소가 존재하지 않으면 여전히 일부 숫자를 반환 할 것입니다. (대부분의 요소가 존재하는지 알기 위해 알고리즘을 쉽게 수정할 수 있습니다)

역사 채널 :이 알고리즘은 1982 년 Boyer, Moore에 의해 발명되었으며 Boyer – Moore 다수당 투표 알고리즘.

이 알고리즘에 대한 회상이 있으며,이 알고리즘은 2K 규칙을 따를 수도 있고 그렇지 않을 수도 있습니다. 함수 호출로 인해 메모리 제한을 깨지 않도록 스택 등으로 다시 작성해야 할 수도 있지만, 그러한 호출의 로그 수가 있기 때문에 불필요 할 수 있습니다. 어쨌든, 나는 대학에서 모호한 회상이나 분열과 정복과 관련된 이에 대한 모호한 솔루션을 가지고 있습니다. . 나누는 기본 규칙은 두 개의 후보자 최고 값을 반환한다는 것입니다. 그 중 하나는 최고 값이고 그 중 하나는 다른 값 (2 위일 수도 있고 아닐 수도 있음)입니다. 알고리즘 자체를 잊어 버립니다.

Jason의 답변이 Buti-Oxa의 답변과 동일하며 설명 된 알고리즘이 작동하는 방식으로 작동한다고 가정하면 Buti-Oxa / Jason Hernandez의 답변에 대한 정확성 증명은 다음과 같습니다.

최고 값이 선택되지 않으면 조정 된 의심 강도를 의심 강도와 동일하게 정의하거나 최고 값이 선택되지 않은 경우. 올바른 숫자를 선택할 때마다, 현재 조정 된 의심 강도는 1만큼 증가합니다. 잘못된 숫자를 선택할 때마다 잘못된 숫자가 현재 선택되었는지에 따라 1 씩 떨어지거나 1만큼 증가합니다. 따라서 가능한 최소 결말 조정 의심 강도는 [상단 값]의 숫자와 같습니다. [기타 값

라이센스 : CC-BY-SA ~와 함께 속성

제휴하지 않습니다 StackOverflow