determinar la ocurrencia más común en una matriz

Question

Supongamos que tengo una serie de dobles que se parece a lo siguiente:

Array[10] = {10, 10, 10, 3, 10, 10, 6, 10, 10, 9, 10} 

Necesito una función que puede determinar lo que el voto majorty está en la matriz, en este caso "10" porque es el número que aparece con más frecuencia ... Y, por supuesto, existe la situación en la que no existe mayoría (donde son iguales), en ese caso necesito lanzar una excepción ...

¿Alguna pista? Además de realizar un bucle desagradable en la matriz (para cada índice, determinar cuántos existen con el mismo valor, almacenar un recuento en la matriz, y luego escanear la matriz de recuento para el número más alto y el valor en esa posición es el ganador , etc.)

Answer 1

El uso de un Map<Integer, Integer> debe ser simple como:

int mostFrequent(int... ary) { 
    Map<Integer, Integer> m = new HashMap<Integer, Integer>(); 

    for (int a : ary) { 
     Integer freq = m.get(a); 
     m.put(a, (freq == null) ? 1 : freq + 1); 
    } 

    int max = -1; 
    int mostFrequent = -1; 

    for (Map.Entry<Integer, Integer> e : m.entrySet()) { 
     if (e.getValue() > max) { 
      mostFrequent = e.getKey(); 
      max = e.getValue(); 
     } 
    } 

    return mostFrequent; 
} 

Answer 2

Su primer problema es que tiene una "matriz de dobles", porque la igualdad es problemática con los datos de punto flotante (los valores numéricos idénticos pueden representarse mediante diferentes patrones de bits, entre otras cosas). Si sus dobles son de hecho (como en el ejemplo) enteros, use int en su lugar. Otra cosa, piense detenidamente en cómo define qué valores son iguales para el propósito de representar el mismo voto.

En cuanto a determinar el voto mayoritario, use un Map con la "clave de voto" como clave y el número de votos como valor, luego, al final, recorra el mapa para encontrar el valor máximo.

Answer 3

Ordene primero la matriz con ordenación rápida y luego digitalice y cuente para obtener una mayoría: O (n ln n). Si el rango de elementos se conoce antes de tiempo, digamos entre {1, k}, entonces se puede usar una clasificación de conteo que se ejecutará en O (n + k).

Como una ligera mejora, mientras escanea la matriz ordenada, si encuentra un valor que tiene más de n/2 ocurrencias, ya está hecho.

Answer 4

Puede hacer esto: convierta su matriz en una lista y oriéntala. Elija el primer índice y llame a lastIndexOf (obj) sobre el valor. Haga esto para cada nuevo valor que encuentre, calcule el rango del valor y almacene los resultados del rango más grande en una variable.

Answer 5

Con una matriz de dobles esto puede no ser fácil ya que las comparaciones de igualdad en dobles son bastante problemáticas. Si usted puede conseguir lejos con el uso de números enteros, se puede hacer algo como lo siguiente:

HashMap<Integer, Integer> map = new HashMap<Integer, Integer>(); 
    for(int element: Array) 
    { 
     Integer frequency = map.get(element); 
     map.put(element, (frequency != null) ? frequency + 1 : 1);  
    } 
    int mostFrequentItem = 0; 
    int[] maxFrequencies = new int[2]; 
    maxFrequencies[0]  = Integer.MIN_VALUE; 

    for(Entry<Integer, Integer> entry: map.entrySet()) 
    { 
     if(entry.getValue()>= maxFrequencies[0]) 
     { 
      mostFrequentItem = entry.getKey(); 
      maxFrequencies[1] = maxFrequencies[0]; 
      maxFrequencies[0] = entry.getValue(); 
     } 
    } 
    if(maxFrequencies[1] == maxFrequencies[0]) 
     throw new Exception();//insert whatever exception seems appropriate 
      return mostFrequentItem 

Esto tendrá un rendimiento de O (n), por lo que debe ser bastante óptima en el comportamiento asintótico. Si sus dobles no son el resultado de cálculos sino que provienen de otra fuente, es decir, si puede estar seguro de que los valores que son básicamente iguales se representarán por igual, puede salirse con la suya usando el mismo método para dobles, sin embargo yo todavía recomiendo tener cuidado de que este sea realmente el caso.

Editar: algunas mejoras de rendimiento como se sugiere en el comentario, así como el apoyo a la comprobación de caso ambiguo

Answer 6

Lo que realmente quiere hacer es contar las apariciones de ciertos elementos en conjunto dado. De hecho, esto fue preguntado hace menos de un día, es posible que desee consultar este very relevant question.

Answer 7

Como @Grizzly señala, los dobles son problemáticas desde un punto de vista computacional.También sugeriría que no tengan sentido desde el punto de vista de tu dominio problemático; ¡Los dobles no tienen ningún sentido con la votación mayoritaria!

Supongamos que 10 y y así sucesivamente son identificadores enteros de las cosas por las cuales la gente está votando. Supongamos también que sabe que los usuarios pueden votar cualquier valor desde 0 hasta 10.

int[] votes = ... 
int[] voteCounts = new int[11]; // 11 could be calculated ... 
for (int vote : votes) { 
    voteCounts[vote]++; 
} 
int majority = (votes.length + 1)/2; 
for (int i = 0; i < voteCounts.length; i++) { 
    if (voteCounts[i] >= majority) { 
     return i; // the winner! 
    } 
} 
throw new NoClearMajorityException(...); 

Este algoritmo es O(N) en el tiempo y O(M) en el espacio, donde M es el más grande identificador. El problema es que solo funciona (como está escrito) si los identificadores son enteros.

Answer 8

simplemente he creado una solución tan hermoso y pequeño con el nuevo Java 8:

import java.util.Arrays; 
import java.util.Collection; 
import java.util.HashMap; 
import java.util.Map; 

public class MostCommonObject { 
    public static void main(String[] args) { 
     System.out.println(mostCommonObject(new Integer[] { -4, 1, -2, 3, 1, -2, 3, 1 })); 
    } 

    public static <T> T mostCommonObject(T[] array) { 
     return mostCommonObject(Arrays.asList(array)); 
    } 

    public static <T> T mostCommonObject(Collection<T> collection) { 
     Map<T, Integer> map = new HashMap<>(); 
     collection.forEach(t -> map.compute(t, (k, i) -> i == null ? 1 : i + 1)); 
     return map.entrySet().stream().max((e1, e2) -> Integer.compare(e1.getValue(), e2.getValue())).get().getKey(); 
    } 
} 

Answer 9

prueba este,

Integer[] array=new Integer[]{10, 10, 10, 3, 10, 10, 6, 10, 10, 9, 10}; 

    List<Integer> demoList=new ArrayList<Integer>(Arrays.asList(array)); 

    Set<Integer> set=new HashSet<Integer>(demoList); 

    Map<Integer,Integer> myMap=new HashMap<Integer, Integer>(); 

    for (Integer integer : set) 
    { 
     int count=Collections.frequency(demoList, integer); 
     myMap.put(count, integer);    
    } 

    int maxOccurance=myMap.get(Collections.max(myMap.keySet()));