Come trovare l’elemento di un array che viene ripetuto almeno N / 2 volte?

Dato un array con N elementi. Sappiamo che uno di questi elementi si ripete almeno N / 2 volte.

Non sappiamo nulla degli altri elementi. Possono ripetersi o possono essere unici.

C’è un modo per scoprire l’elemento che si ripete almeno N / 2 volte in un singolo passaggio o può essere O (N)?

Non è necessario utilizzare spazio aggiuntivo.

st0le ha risposto alla domanda, ma ecco un’implementazione di 5 minuti:

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

Ed ecco una spiegazione divertente (più divertente che leggere la carta, almeno): http://userweb.cs.utexas.edu/~moore/best-ideas/mjrty/index.html

Come gli altri utenti hanno già pubblicato l’algoritmo, non lo ripeterò. Tuttavia, fornisco una semplice spiegazione sul perché funziona:

Si consideri il diagramma seguente, che è in realtà un diagramma di luce non polarizzata:

frecce che si irradiano dal centro

Ogni freccia dal centro rappresenta un candidato diverso. Immagina un punto da qualche parte su una freccia che rappresenta il contatore e il candidato. Inizialmente il contatore è a zero, quindi inizia al centro.
Quando viene trovato il candidato corrente, si sposta di un passo nella direzione di quella freccia. Se viene trovato un valore diverso, il contatore si sposta di un passo verso il centro.
Se c’è un valore di maggioranza, più della metà delle mosse sarà verso quella freccia, e quindi l’algoritmo terminerà con il candidato corrente che è il valore di maggioranza.

Algoritmo di voto della maggioranza di Boyer-Moore

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

Questo codice è un’implementazione simile al modo in cui troviamo la maggior parte di un elemento

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

Non sembra ansible contare nulla senza usare spazio extra. Devi memorizzare almeno un contatore da qualche parte. Se intendi dire che non puoi usare più di O (n) spazio allora dovrebbe essere abbastanza facile.

Un modo sarebbe quello di creare un secondo elenco di soli oggetti unici dall’elenco originale. Quindi, creare un terzo elenco della stessa lunghezza del secondo con un contatore per il numero di occorrenze di ciascun elemento nell’elenco.

Un altro modo sarebbe quello di ordinare l’elenco, quindi trovare la sezione contigua più grande.

Usando la modifica suggerita da ffao a Davi, rispondi:

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

Prova questo :

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

L’algoritmo di voto della maggioranza di Boyer-Moore non riesce a trovare la maggioranza corretta negli array di input sottostanti

numeri int [SIZE] = {1,2,3,4,1,2,3,4,1,2,3,4};

numeri int [SIZE] = {1,2,3,4,1,2,3,4,1,2,3,4,1};