如何找到至少重复 N/2 次的数组元素? [英] How to find the element of an array that is repeated at least N/2 times?

问题描述

给定一个包含 N 个元素的数组.我们知道其中一个元素至少重复了 N/2 次.

Given an array with N elements. We know that one of those elements repeats itself at least N/2 times.

我们对其他元素一无所知.它们可能重复，也可能是唯一的.

We don't know anything about the other elements . They may repeat or may be unique .

有没有办法找出在单次传递中至少重复 N/2 次或者可能是 O(N) 的元素?

Is there a way to find out the element that repeats at least N/2 times in a single pass or may be O(N)?

不要使用额外的空间.

推荐答案

st0le 回答了这个问题，但这是一个 5 分钟的实施:

st0le answered the question, but here's a 5minute implementation:

#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
",current_candidate,counter);
        } else if (counter == 0) {
            current_candidate = arr[i];
            ++counter;
            printf("candidate: %i, counter: %i
",current_candidate,counter);
        } else {
            --counter;
            printf("candidate: %i, counter: %i
",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
", boyerMoore(numbers));
    return 0;
}

这里有一个有趣的解释(至少比阅读论文更有趣):http://userweb.cs.utexas.edu/~moore/best-ideas/mjrty/index.html

And here's a fun explanation (more fun than reading the paper, at least): http://userweb.cs.utexas.edu/~moore/best-ideas/mjrty/index.html

这篇关于如何找到至少重复 N/2 次的数组元素?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！