N/2번 이상 반복되는 배열의 요소를 찾는 방법은?

N/2번 이상 반복되는 배열의 요소를 찾는 방법은?

N개의 요소로 구성된 배열이 주어집니다.우리는 그 요소들 중 하나가 적어도 N/2번 반복된다는 것을 알고 있습니다.

우리는 다른 요소들에 대해서는 아무것도 모릅니다.반복될 수도 있고 유일할 수도 있습니다.

한 번의 패스로 최소 N/2회 반복되는 요소 또는 O(N)일 수 있는 요소를 알아낼 수 있는 방법이 있습니까?

여분의 공간은 사용할 수 없습니다.

다른 사용자들이 이미 알고리즘을 올렸기 때문에 반복하지 않겠습니다.그러나 작동하는 이유에 대해 간단한 설명을 드립니다.

편광되지 않은 빛의 도표인 다음의 도표를 생각해 보십시오.

중앙의 각 화살표는 서로 다른 후보를 나타냅니다.카운터와 후보를 나타내는 화살표의 어딘가에 있는 점을 상상해 보십시오.처음에는 카운터가 0이므로 중앙에서 시작합니다.
현재 후보가 발견되면 해당 화살표 방향으로 한 단계 이동합니다.다른 값이 발견되면 카운터가 중앙으로 한 걸음 이동합니다.
과반수 값이 있으면 절반 이상의 움직임이 해당 화살표를 향하게 되고, 따라서 알고리즘은 현재 후보가 다수 값이 되는 것입니다.

st0le은 질문에 답했지만, 여기 5분간의 구현이 있습니다.

#include <stdio.h>

#define SIZE 13

int boyerMoore(int arr[]) {
    int current_candidate = arr[0], counter = 0, i;
    for (i = 0; i < SIZE; ++i) {
        if (current_candidate == arr[i]) {
            ++counter;
            printf("candidate: %i, counter: %i\n",current_candidate,counter);
        } else if (counter == 0) {
            current_candidate = arr[i];
            ++counter;
            printf("candidate: %i, counter: %i\n",current_candidate,counter);
        } else {
            --counter;
            printf("candidate: %i, counter: %i\n",current_candidate,counter);
        }
    }
    return current_candidate;
}

int main() {
    int numbers[SIZE] = {5,5,5,3,3,1,1,3,3,3,1,3,3};
    printf("majority: %i\n", boyerMoore(numbers));
    return 0;
}

그리고 여기 재미있는 설명이 있습니다 (적어도 신문을 읽는 것보다 더 재미있습니다): http://userweb.cs.utexas.edu/ ~june/best-best-best/differenty/index.june

보이어-무어 다수결 알고리즘

//list needs to have an element with a count of more than n/2 throughout itself for
//this algorithm to work properly at all times.

lst = [1,2,1,2,3,1,3,3,1,2,1,1,1]

currentCount = 0
currentValue = lst[0]
for val in lst:
   if val == currentValue:
      currentCount += 1
   else:
      currentCount -= 1

   if currentCount == 0:
      currentValue = val
      currentCount = 1


print(currentValue)

이 코드는 우리가 요소의 대부분을 찾는 방법과 유사한 구현입니다.

int find(int* arr, int size)
{ 
int count = 0, i, m;
  for (i = 0; i < size; i++) 
  {
    if (count == 0)
        m = arr[i];
    if (arr[i] == m) 
        count++;
    else
        count--;
   }
    return m;
}

여분의 공간을 사용하지 않고서는 아무것도 셀 수 없을 것 같습니다.카운터는 적어도 한 개는 어딘가에 보관해야 합니다.O(n)개 이상의 공간을 사용할 수 없다고 말하는 경우에는 상당히 쉬운 방법이어야 합니다.

한 가지 방법은 원래 목록에서 고유 개체만 두 번째 목록을 만드는 것입니다.그런 다음 목록에 있는 각 항목의 발생 횟수에 대한 카운터를 사용하여 두 번째와 동일한 길이의 세 번째 목록을 만듭니다.

다른 방법은 목록을 정렬한 다음 가장 큰 연속 섹션을 찾는 것입니다.

다비에게 ffao가 제안한 수정사항을 사용하면 다음과 같이 대답할 수 있습니다.

public class MaxRepeated {

    public static void main(final String[] args) {
        maxRepeatedElement(new int[]{1, 2, 1, 2, 3, 2, 3, 1});
        maxRepeatedElement(new int[]{1, 2, 1, 2, 3, 1, 3, 1});
        maxRepeatedElement(new int[]{1, 2, 1, 2, 4, 1, 1, 3, 1, 3, 1});
        maxRepeatedElement(new int[]{1, 2, 1, 2, 2, 1, 2, 3, 1, 2, 1, 2});
    }

    private static int maxRepeatedElement(final int[] arr) {

        int current_candidate = arr[0];
        int previous_candidate = arr[0];
        int counter = 0, i;
        for (i = 0; i < arr.length; ++i) {
            if (current_candidate == arr[i]) {
                ++counter;
            } else if (counter == 0) {
                previous_candidate = current_candidate;
                current_candidate = arr[i];
                ++counter;
            } else {
                --counter;
            }
            System.out.printf("  candidate: %d, counter: %d\n", current_candidate, counter);
        }

        if (counter == 0) {
            System.out.printf(" possible: %d or %d with net freq %d \n", current_candidate, previous_candidate, counter);
            final int f1 = frequency(arr, current_candidate);
            final int f2 = frequency(arr, previous_candidate);
            final int halfLen = arr.length / 2 + (arr.length % 2 == 0 ? 0 : 1);
            if (f1 >= halfLen || f2 >= halfLen) {
                if (f1 > f2) {
                    System.out.printf("majority: %d with freq %d \n", current_candidate, f1);
                } else {
                    System.out.printf("majority: %d with freq %d \n", previous_candidate, f2);
                }
            } else {
                System.out.printf("NO majority! \n");
            }
        } else {
            System.out.printf("majority: %d with freq %d \n", current_candidate, frequency(arr, current_candidate));
        }
        return current_candidate;
    }

    private static int frequency(final int[] arr, final int candidate) {
        int counter = 0;
        for (int c : arr) {
            counter += candidate == c ? 1 : 0;
        }
        return counter;
    }
}

시도해 보기:

#include<iostream>
using namespace std;
int main()
{
    int counter=0;
    int a[]={10, 11, 5, 27, 4, 2, 7, 5, 7, 11, 9, 5, 5, 4, 10, 7, 5, 3, 7, 5};
    for(int i = 0; i < 20; i++)
    {
        if(a[i]==5)
        counter++;
    }
    cout << "it appears " << counter << " times";
}

보이어-무어 다수결 알고리즘이 아래 입력 배열에서 올바른 다수결을 찾지 못합니다.

인트 수[숫자]SIZE] = {1,2,3,4,1,2,3,4,1,2,3,4};

인트 수[숫자]SIZE] = {1,2,3,4,1,2,3,4,1,2,3,4};

언급URL : https://stackoverflow.com/questions/3740371/how-to-find-the-element-of-an-array-that-is-repeated-at-least-n-2-times