Wie gibt man nur ArrayList von Strings mit minimaler Anzahl von Vorkommen zurück?

Question

Ich habe eine String[], originalStringArray, die Duplikate in ihnen hat. Also {"dog","cat","dog","fish","dog","cat"}.

Ich wollte eine Funktion machen, die nur die Strings zurückgibt, die genau eine bestimmte Anzahl von Malen auftreten. Wenn ich hier 3 sagte, würde ich "Hund", aber nicht "Katze" zurückgeben.

Hier ist mein aktueller Code:

public ArrayList<String> returnMultiples(String[] originalStringArray,int requiredCount){ 
    ArrayList<Integer> mCount = new ArrayList<>(); 
    List<String> list = Arrays.asList(originalStringArray); 
    ArrayList<String> result = new ArrayList<>(); 

    // Count occurrences in original string 
    for(String item: originalStringArray){ 
     mCount.add(Collections.frequency(list,item)); 
    } 

    // If frequency is equal to count, add to array list 
    for(int i=0; i<mCount.size(); i++){ 
     if(mCount.get(i) == requiredCount){ 
      result.add(originalStringArray[i]); 
     } 
    } 

    return result; 
} 

Das Problem, das ich habe ist, dass ich irgendwo gelesen, dass die Sammlungen Bibliothek ist sehr langsam und zieht, und es scheint auch, wie, dass diese Methode HashSets und Tabellen reduziert wird unter Verwendung von . Leider weiß ich nicht, wie ich das machen soll. Gibt es einen besseren Weg, dies zu tun?

Answer 1

Irgendeine Art von Karte wird benötigt, um dies auszuführen. Hier ist ein Beispiel unter Verwendung von HashMaps geschrieben:

public ArrayList<String> returnMultiples(String[] array, int min){ 
    HashMap<String, Integer> counts = new HashMap<String, Integer>();//instantiate a new HashMap 

    //loop through the array and count the occurrences of each different string in the array 
    for(int i = 0; i < array.length; i++){ 
     String word = array[i]; 
     if(counts.containsKey(word)) 
      counts.put(word, counts.get(word) + 1); 
     else 
      counts.put(word, 1); 
    } 

    ArrayList<String> multiples = new ArrayList<String>(); 

    //check if any of the words occur >= min times. if so, add them to the returning list. 
    for(String key : counts.keySet()){ 
     if(counts.get(key) >= min){ 
      multiples.add(key); 
     } 
    } 

    return multiples;//return the list we just created of the desired strings 
} 

von der Länge der Saiten Je wird die HashMap ein wenig effizienter als Sammlungen mit, obwohl der Unterschied meist vernachlässigbar ist.

Answer 2

Sie müssen HashMap für diese Aufgabe verwenden.

sagen Lässt Ihre HashMap Anzahl der Vorkommen von bestimmten Zeichenfolge enthalten wird, so wird es vom Typ sein HasMap<String,Integer>

Und jetzt lässt Iterierte über Ihre Sammlung:

1. eine andere Zeichenfolge aus Ihrer Sammlung Get
2. überprüfen Sie, ob geben Zeichenfolge existiert in HashMap (#contains)
3. Falls nicht vorhanden, neues Element setzen mit String-Taste (hashMap.put (stringKey, 1);
4. Wenn es vorhanden ist, setzen Element mit dem gleichen Schlüssel, sondern erhöht den internen Zähler (hashMap.put (stringKey, hashMap.get (stringKey) + 1)
5. Weiter

Jetzt haben Sie hashmap enthält genaue Anzahl der Vorkommen bestimmter Strings aus Ihren Sammlungen.

Fast Lookup wäre, um HashMap<Integer,String> umgekehrte zu erstellen, aber es gibt eine Möglichkeit, dass die Anzahl verdoppelt und dies wird nicht funktionieren. Um die Zeichenfolge, die auftritt, mit der angegebenen Zeichenfolge zu vergleichen, müssen Sie alle Schlüssel der Karte durchlaufen und nur diejenigen zurückgeben, deren Anzahl Ihren Kriterien entspricht.

Answer 3

Ihr Algorithmus wird Duplikate zurückgeben.

Ein HashSet ist Teil der Sammlungen Bibliothek, also kein Vorteil für Sie dort.

Ihre Schleife mit Collections.frequency ist ein O (n^2) -Algorithmus. (für jeden String in originalStringArray Collections.frequency loops erneut über das gesamte originalStringArray).

Sie könnten es mit nur einer HashMap tun.

Inkrementieren Sie eine Ganzzahl in der Zuordnung für jeden String in originalStringArray.

Entfernen Sie alle Schlüssel mit einem anderen Wert als requiredCount.

Fügen Sie die map.keySet() zu einer neuen ArrayList hinzu, wenn Sie eigentlich eine ArrayList zurückgeben wollten.

oder map.keySet(). ToArray (String [map.size()]), wenn Sie ein Array möchten.

Answer 4

Sie könnten eine AVL Tree verwenden, die Prämisse wäre, dass, wenn Sie sagen wir 1.000.000 Elemente in Ihrem Array hätte 1,000,000 steps, um durch diese Datenstruktur zu gehen. Mit einem AVL Tree würde es O(Log (1,000,000)) Schritte nehmen, die == 6 Schritte sind, ziemlich ordentlich. Dies wäre ein guter Ansatz, wenn Ihre Daten dynamisch wären, obwohl Sie Einfügungen optimieren müssten.

Mit einem AVL-Baum würde alles sortiert werden, so erhalten Sie O(Log N) Zeit. Statt wie so für N Steps durch eine Anordnung quert:

Man könnte so etwas wie so haben:

Wo es die Wurzel überprüft und sieht, dass die Char c größer als die erste Char in dog, und Transvers links. Im Wesentlichen schneiden Suchzeit von 1/2 Schritt macht es O(Log N) Schritte. Sie müssen die Baumhöhe ausgeglichen halten.

Das Schöne an einem AVL Tree ist, dass Ihre Daten immer in sortierter Reihenfolge sind, da der Baum ausgewogen sein muss. Wenn sich die Daten nicht so oft ändern und Sie keine sortierten Daten benötigen, ist es wahrscheinlich besser, eine HashMap zu verwenden.

Answer 5

Ich denke, effizient genug sein wird, Hash-Karten zu verwenden.

Shortest-Code, der meine Gedanken kommt (und die HashMaps verwendet) wird wie folgt aussehen:

String[] filter(String[] collection, int requirement) { 
    final HashMap<String, Integer> temp = new HashMap<>(); 

    for (String item : collection) { 
     int current = temp.getOrDefault(item, 0); 
     temp.put(item, ++current); 
    } 

    final Iterator<Entry<String, Integer>> iterator = temp.entrySet().iterator(); 
    while (iterator.hasNext()) { 
     final Entry<String, Integer> entry = iterator.next(); 
     if (entry.getValue() != requirement) { 
      iterator.remove(); 
     } 
    } 

    return temp.keySet().toArray(new String[temp.size()]); 
} 

Was verwendet werden können, wie folgt:

final String[] array = new String[]{ 
    "dog", "dog", "dog", "cat", "cat", "fish", "cat" 
}; 

final String[] result = filter(array, 3); 

for (String item : result) { 
    System.out.println(item); 
} 

Und Ausgabe erzeugt wie erwartet:

cat

Hund