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

Question

Dada 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 una sola pasada o puede ser O (N)?

No se debe usar espacio adicional.

Answer 1

st0le responde a la pregunta, pero aquí es una implementación de 5 minutos:

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

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

Answer 2

The Boyer-Moore Majority Vote Algorithm

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

Answer 3

No parece posible contar nada sin utilizar espacio adicional. 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 los únicos 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.

Answer 4

Como los otros usuarios ya tienen publicado el algoritmo, no voy a repetir eso. Sin embargo, proporciono una explicación simple de por qué funciona:

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

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 de mayoría, 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 de la mayoría.

Answer 5

La Boyer-Moore mayoría de votos Algoritmo no encuentra mayor parte correcta en las matrices de entrada por debajo de

números int [TAMAÑO] = {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};

Answer 6

Este código es una aplicación similar a la forma en la que se encuentra 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; 
} 

Answer 7

Utilizando la modificación sugerida por ffao a Davi'd respuesta:

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

Answer 8

Prueba esto :

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