Najbardziej efektywny sposób zamówić tablicę łańcuchów poprzez częstotliwość

Question

Mam tablicę łańcuchów:

String[] stringArray = {"x", "y", "z", "x", "x", "y", "a"}; 

Co jest najszybszym/najbardziej skuteczny sposób, aby zamówić ten w mniejszym Collection w kolejności jak częste każdego String jest z częstotliwością?

I choć o użyciu String jako klucz w HashMap<String,Integer> ale to nie byłby być klasyfikowane pod względem częstotliwości

Mój inny sposób i uważane jest za pomocą TreeMap<Integer, String[]> z listy ciągów z tej liczby całkowitej, ale wydaje wiele kontroli dotyczy ..

Próbuję uniknąć użycia więcej niż jednej pętli Jeśli to możliwe, moje tablice String będą znacznie większe niż te powyżej. Dzięki!

EDIT Co chcę tylko, aby móc wysyłać Ciągi w kolejności częstotliwości, a korzystnie móc sparować ten ciąg z częstotliwością w tablicy, więc na przykład dwóch tablic wyjściowych:

["x", "y", "z", "a"] 
[3,2,1,1] 

byłoby to dość prosty problem, jeśli prędkość nie było problemem, dlatego pytam wielkie umysły tutaj :)

Answer 1

Problem ten można rozwiązać na dwa etapy:

1. Utworzyç licznika obiektu - Map<String, Integer> wpis dla każdej struny, ile razy pojawia się w wejściu: innymi słowy, jest to mapa częstotliwość . Jest to O(n), ponieważ wystarczy tylko raz przejść przez wejście, aby zbudować mapę, tworząc mapę

2. Z poprzednią mapą utwórz listę z jej kluczami, posortowaną przy użyciu częstotliwości elementów (wartości na mapie) jako kryteriów zamówienia .To O(n log n), można nazwać Collections.sort(), z Comparator który wykorzystuje częstotliwość ciąg do porównań

To, co mam na myśli:

String[] stringArray = {"x", "y", "z", "x", "x", "y", "a"}; 

final Map<String, Integer> counter = new HashMap<String, Integer>(); 
for (String str : stringArray) 
    counter.put(str, 1 + (counter.containsKey(str) ? counter.get(str) : 0)); 

List<String> list = new ArrayList<String>(counter.keySet()); 
Collections.sort(list, new Comparator<String>() { 
    @Override 
    public int compare(String x, String y) { 
     return counter.get(y) - counter.get(x); 
    } 
}); 

Po powyższy kod wykonywany, zmienna list będzie zawierać następujące wartości (kolejność między elementami o tej samej częstotliwości jest nieokreślona):

[x, y, a, z] 

To trywialne do konwersji listy do tablicy:

list.toArray(new String[list.size()]) 

A jeśli chcesz dowiedzieć się częstotliwość każdej struny, po prostu iteracyjne nad segregowanych klawiszy:

for (String str : list) { 
    int frequency = counter.get(str); 
    System.out.print(str + ":" + frequency + ", "); 
} 

Answer 2

Użyj HashMap<String,Integer> aby utrzymać swoje liczby. Będzie to najbardziej efektywny sposób przetwarzania dowolnej listy łańcuchów.

Utwórz ArrayList<Map.Entry<String,Integer>> z mapy entrySet().

Sortuj tę listę, korzystając z Collections.sort() i niestandardowego komparatora.

Nie daj się zwieść na mikro-optymalizacje.

Answer 3

String[] stringArray = {"x", "y", "z", "x", "x", "y", "a"}; 

List<String> list = Arrays.asList(stringArray); 
Collections.sort(list); 

HashMap<String, Integer> map = new HashMap<String, Integer>(); 

for(int i = 0; i < list.size();) { 

    String s = list.get(i); //get the string to count 

    int count = list.lastIndexOf(s) - list.indexOf(s) + 1; //count it 

    map.put(s, count); // add it 

    i = list.lastIndexOf(s) + 1; // skip to the next string 

} 

bym potraktuj to jako eleganckie rozwiązanie, ale nie wiem, jak to działa. Jeśli je posortujesz, użyj mapy drzewa, ale to naprawdę wolno.

można sortować je potem tak:

TreeMap<String, Integer> sortedMap = new TreeMap<String, Integer>(unsortedMap); 

Należy jednak pamiętać, że posiadanie Integer jako klucz nie działa! Ponieważ klucz jest unikalny i jeśli na przykład a i b pojawią się jeden raz, a zostanie wyrzucony!

Answer 4

Jeśli biblioteki innych firm są uczciwa gra, następujących jedna wkładka z Guava jest asymptotycznie optymalne:

Multisets.copyHighestCountFirst(ImmutableMultiset.copyOf(array)) 
    .elementSet().toArray(new String[0]); 

Answer 5

Drukuj wynik: 1) łańcuch z innym wystąpieniu uporządkowane malejąco. 2) ciąg znaków z tym samym wystąpieniem posortowane według char w kolejności asce.

public static void sortStringByOccurance(String[] stringArray) { 
    // O(n) 
    Map<String, Integer> map = new HashMap<>(); 
    for (String str : stringArray) { 
     map.put(str, map.containsKey(str)? map.get(str)+1 : 1); 
    } 

    // O(n) 
    TreeMap<Integer, TreeSet<String>> treemap = new TreeMap<>(); 
    for (String key : map.keySet()) { 
     if (treemap.containsKey(map.get(key))) { 
      treemap.get(map.get(key)).add(key); 
     } 
     else { 
      TreeSet<String> set = new TreeSet<>(); 
      set.add(key); 
      treemap.put(map.get(key), set); 
     } 
    } 

    // O(n) 
    Map<Integer, TreeSet<String>> result = treemap.descendingMap(); 
    for (int count : result.keySet()) { 
     TreeSet<String> set = result.get(count); 
     for (String word : set) { 
      System.out.println(word + ":" + count); 
     } 
    } 
}