Wie finde ich das Element eines Arrays, das mindestens N/2 Mal wiederholt wird?

Gegeben sei ein Array mit N Elementen. Wir wissen, dass sich eines dieser Elemente mindestens N/2 Mal wiederholt.

Über die anderen Elemente wissen wir nichts. Sie können sich wiederholen oder einmalig sein.

Gibt es eine Möglichkeit, das Element herauszufinden, das sich mindestens N/2 Mal in einem einzigen Durchgang wiederholt oder O (N) sein kann?

Es darf kein zusätzlicher Platz verwendet werden.

Da die anderen Benutzer den Algorithmus bereits gepostet haben, werde ich das nicht wiederholen. Ich gebe jedoch eine einfache Erklärung, warum es funktioniert:

Betrachten Sie das folgende Diagramm, das eigentlich ein Diagramm von unpolarisiertem Licht ist:

Jeder Pfeil von der Mitte repräsentiert einen anderen Kandidaten. Stellen Sie sich einen Punkt irgendwo auf einem Pfeil vor, der den Zähler und den Kandidaten darstellt. Anfangs steht der Zähler auf Null, also beginnt er in der Mitte.
Wenn der aktuelle Kandidat gefunden ist, bewegt er sich einen Schritt in Richtung dieses Pfeils. Wird ein anderer Wert gefunden, bewegt sich der Zähler einen Schritt in Richtung Mitte.
Wenn es einen Mehrheitswert gibt, werden mehr als die Hälfte der Bewegungen in Richtung dieses Pfeils gehen, und daher wird der Algorithmus damit enden, dass der aktuelle Kandidat der Mehrheitswert ist.

st0le hat die Frage beantwortet, aber hier ist eine 5-Minuten-Implementierung:

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

Und hier ist eine lustige Erklärung (mehr Spaß als das Lesen der Zeitung zumindest): http://userweb.cs.utexas.edu/~moore/best-ideas/mjrty/index.html

Der Boyer-Moore Mehrheitsabstimmungsalgorithmus

//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)

Dieser Code ist eine ähnliche Implementierung wie wir den Großteil eines Elements finden

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

Es scheint nicht möglich zu sein, etwas zu zählen, ohne zusätzlichen Platz zu verwenden. Sie müssen mindestens einen Zähler irgendwo speichern. Wenn Sie sagen wollen, dass Sie nicht mehr als O (n) Speicherplatz verwenden können, sollte es ziemlich einfach sein.

Eine Möglichkeit wäre, eine zweite Liste nur mit eindeutigen Objekten aus der ursprünglichen Liste zu erstellen. Erstellen Sie dann eine dritte Liste mit der gleichen Länge wie die zweite mit einem Zähler für die Anzahl der Vorkommen jedes Elements in der Liste.

Eine andere Möglichkeit wäre, die Liste zu sortieren und dann den größten zusammenhängenden Abschnitt zu finden.

Unter Verwendung der von ffao vorgeschlagenen Änderung an Davi würde antworten:

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

Versuche dies :

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