Określić najbardziej powszechnym zjawiskiem w tablicy

Question

Przyjmijmy, mam tablicę podwaja, który wygląda tak:

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

Potrzebuję funkcji, które można określić, co głosowanie MAJORTY jest w tablicy, w tym przypadku "10", ponieważ jest to liczba, która pojawia się najczęściej ... I oczywiście jest sytuacja, w której nie ma większości (gdzie są równe), w tym przypadku muszę rzucić wyjątek ...

Jakieś wskazówki? Oprócz wykonywania naprawdę nieprzyjemnych pętli w tablicy (dla każdego indeksu określ, ile istnieje z tą samą wartością, przechowuj liczbę w tablicy, a następnie skanuj tablicę liczników dla największej liczby, a wartość na tej pozycji jest zwycięzcą , itd ...)

Answer 1

Korzystanie z Map<Integer, Integer> powinny być proste, jak:

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

Twój pierwszy problem polega na tym, że masz "tablicę podwójnych", ponieważ równość jest problematyczna w przypadku danych zmiennoprzecinkowych (identyczne wartości liczbowe mogą być reprezentowane między innymi przez różne wzory bitowe). Jeśli twoje duble są w rzeczywistości (jak w przykładzie) liczbami całkowitymi, użyj zamiast tego int. Innymi słowy, zastanówcie się długo, jak określić, jakie wartości są równe w celu reprezentowania tego samego głosu.

Jeśli chodzi o ustalanie większości głosów, należy użyć Map z "id głosowania" jako kluczem i liczbą głosów jako wartością - następnie na końcu należy przejść przez mapę, aby znaleźć maksymalną wartość.

Answer 3

Posortuj najpierw tablicę z/szybko sortuj, a następnie zeskanuj i policz do większości - O (n ln n). Jeśli zakres elementów jest znany z wyprzedzeniem, powiedzmy między {1, k}, można zastosować sortowanie liczące, które będzie działało w O (n + k).

Jako niewielką poprawę, gdy skanujesz posortowaną tablicę, jeśli znajdziesz wartość, która ma więcej niż n/2 wystąpień, skończysz.

Answer 4

Można to zrobić: Konwertuj tablicę na listę i ją posortuj. Wybierz pierwszy indeks i wywołaj lastIndexOf (obj) na wartości. Zrób to dla każdej nowej wartości, którą napotkasz, obliczyć zakres wartości i zapisać wyniki największego zakresu w zmiennej.

Answer 5

Z wieloma sobowtórami może to nie być łatwe, ponieważ porównania równości w deblu są dość problematyczne. Jeśli można uciec z użyciem liczb całkowitych, można zrobić coś jak poniżej:

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 

to będzie musiało O (n) wydajności, więc powinno być całkiem optymalne asymptotycznej zachowanie wydajności. Jeśli twoje duble nie są wynikiem obliczeń, ale pochodzą z innego źródła, to znaczy, jeśli możesz być pewny, że wartości, które są w zasadzie takie same, będą reprezentowane jednakowo, możesz uciec z użyciem tej samej metody dla deblu, jednak nadal zalecamy uważać, że tak jest naprawdę.

Edycja: niektóre ulepszenia wydajności, jak je w komentarzu, a także wspieranie sprawdzania niejednoznacznym przypadku

Answer 6

Co naprawdę chcesz zrobić, to zliczyć wystąpienia niektórych elementów w danym zestawie. W rzeczywistości było to wcześniej zadawane mniej niż dzień temu, możesz zajrzeć do tego very relevant question.

Answer 7

Jak @Grizzly wskazuje debel są problematyczne z punktu widzenia obliczeniowego.Sugerowałbym również, że nie mają one sensu z punktu widzenia twojej domeny problemów; debel nie ma sensu z większością głosów!

Pozwala więc założyć, że 10 i 6 i tak dalej są liczbami całkowitymi dla rzeczy, za które ludzie głosują. Załóżmy również, że wiesz, że użytkownicy mogą głosować dowolną wartość z 0 do 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(...); 

Algorytm ten jest O(N) w czasie i przestrzeni w O(M), gdzie M to największa identyfikator. Połów jest taki, że działa tylko (tak jak zapisano), jeśli identyfikatory są liczbami całkowitymi.

Answer 8

Właśnie stworzył taki piękny i małe rozwiązanie z nowym 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

próbować ten jeden,

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()));