¿Cómo encontrar el elemento de una matriz que se repite al menos N / 2 veces?

Dado una matriz con N elementos. Sabemos que uno de esos elementos se repite al menos N / 2 veces.

No sabemos nada sobre los otros elementos. Pueden repetir o pueden ser únicos.

¿Hay alguna manera de descubrir el elemento que se repite al menos N / 2 veces en un solo paso o puede ser O (N)?

No se debe usar espacio extra.

st0le respondió la pregunta, pero aquí hay una implementación de 5 minutos:

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

Y aquí hay una explicación divertida (más divertida que leer el periódico, al menos): http://userweb.cs.utexas.edu/~moore/best-ideas/mjrty/index.html

Como los otros usuarios ya han publicado el algoritmo, no lo repetiré. Sin embargo, ofrezco una explicación simple de por qué funciona:

Considere el siguiente diagtwig, que en realidad es un diagtwig de luz no polarizada:

flechas que irradian desde el centro

Cada flecha del centro representa un candidato diferente. Imagine un punto en alguna parte de una flecha que represente el contador y el candidato. Inicialmente, el contador está en cero, por lo que comienza en el centro.
Cuando se encuentra el candidato actual, se mueve un paso en la dirección de esa flecha. Si se encuentra un valor diferente, el contador se mueve un paso hacia el centro.
Si hay un valor mayoritario, más de la mitad de los movimientos se dirigirán hacia esa flecha, y por lo tanto el algoritmo terminará con el candidato actual siendo el valor mayoritario.

El algoritmo de voto mayoritario de 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) 

Este código es una implementación similar a la forma en que encontramos la mayoría de 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; } 

No parece posible contar nada sin usar espacio extra. Tienes que almacenar al menos un contador en alguna parte. Si quiere decir que no puede usar más de O (n) espacio, entonces debería ser bastante fácil.

Una forma sería crear una segunda lista de solo objetos únicos de la lista original. Luego, cree una tercera lista de la misma longitud que la segunda con un contador para el número de ocurrencias de cada elemento en la lista.

Otra forma sería ordenar la lista y luego buscar la sección contigua más grande.

Usando la modificación sugerida por ffao a la respuesta de Davi:

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

Prueba esto :

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

El algoritmo de voto mayoritario de Boyer-Moore no puede encontrar la mayoría correcta en las matrices de entrada a continuación

números enteros [SIZE] = {1,2,3,4,1,2,3,4,1,2,3,4};

números enteros [SIZE] = {1,2,3,4,1,2,3,4,1,2,3,4,1};