Come restituire solo ArrayList di stringhe con il numero minimo di occorrenze?

Question

Ho un String[], originalStringArray, che ha duplicati in loro. Quindi {"dog","cat","dog","fish","dog","cat"}.

Volevo creare una funzione che restituisca solo le stringhe che si verificano esattamente un certo numero di volte. Per qui, se ho detto 3, restituirebbe "cane" ma non "gatto".

Ecco il mio codice corrente:

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

Il problema che ho è, ho letto da qualche parte che la biblioteca Collezioni è molto lento e trascinare, e sembra anche che questo metodo potrebbe essere ridotto utilizzando HashSets e tabelle . Sfortunatamente, sono piuttosto incerto su come farlo. C'è un modo migliore per farlo?

Answer 1

Una sorta di mappa sarà necessaria per eseguire questa operazione. Ecco un esempio scritto utilizzando HashMaps:

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 
} 

A seconda della lunghezza delle corde, il HashMap sarà un po 'più efficiente di utilizzare le collezioni anche se la differenza è in gran parte trascurabile.

Answer 2

Per questa attività è necessario utilizzare HashMap.

permette di dire la tua HashMap conterrà conteggio delle occorrenze di data stringa, quindi sarà di tipo HasMap<String,Integer>

E ora, lascia iterare sopra la vostra collezione:

1. ottenere un'altra stringa dalla tua collezione
2. Controllare se la stringa dare esiste in HashMap (#contains)
3. Se non esiste, mettere nuovo elemento con chiave String (hashMap.put (stringKey, 1);
4. Se esiste, mettere elemento con la stessa chiave, ma incrementare il contatore interno (hashMap.put (stringKey, hashMap.get (stringKey) +1)
5. Continua

Ora avete hashmap contiene esatto numero di occorrenze di stringhe date dalle tue raccolte.

La ricerca rapida sarebbe quella di creare inverso HashMap<Integer,String> ma c'è una possibilità che i conteggi duplicheranno e questo non funzionerà. Per ottenere la stringa che le occorrenze corrisponde alla stringa specificata, dovrai eseguire un'iterazione su tutte le chiavi della mappa e restituire solo quelle con cui il conteggio delle occorrenze corrisponde ai tuoi criteri.

Answer 3

L'algoritmo restituirà i duplicati.

Un Hashset è parte della libreria Raccolte, quindi nessun vantaggio per voi.

Il ciclo che contiene Collections.frequency è un algoritmo O (n^2). (per ogni stringa in originalStringArray Collections.frequency esegue nuovamente il loop su originalStringArray).

Si potrebbe fare solo con una HashMap.

Incrementa un numero intero nella mappa per ogni stringa in OriginalStringArray.

Rimuovere tutte le chiavi con un valore diverso da requiredCount.

Aggiungere il map.keySet() a un nuovo ArrayList, se si intende effettivamente restituire un ArrayList.

o map.keySet(). ToArray (String [map.size()]) se si desidera un array.

Answer 4

È possibile utilizzare uno AVL Tree, la premessa sarebbe che se avessi diciamo 1.000.000 articoli nel tuo array ci vorrebbe 1,000,000 steps per passare attraverso quella struttura di dati. Con uno AVL Tree ci vorrebbero i passi O(Log (1,000,000)) che sono i passi == 6, abbastanza ordinati. Questo sarebbe un buon approccio se i tuoi dati fossero dinamici, anche se dovresti ottimizzare gli inserimenti.

Con un albero AVL, tutto viene ordinato, quindi è possibile ottenere il tempo O(Log N). Invece di transversing attraverso una serie in questo modo per N Steps:

si potrebbe avere qualcosa in questo modo:

Dove controlla la radice e vede che il Char c è maggiore di il primo Char in dog e le trasversali a sinistra. Essenzialmente riducendo il tempo di ricerca di 1/2 ogni passo rendendolo passo O(Log N). Devi mantenere l'altezza dell'albero equilibrata.

La cosa bella di un AVL Tree è che i dati sono sempre ordinati, poiché l'albero deve essere bilanciato.

Se i dati non cambiano spesso e non è necessario disporre di dati ordinati, è preferibile utilizzare lo HashMap.

Answer 5

Suppongo che sia abbastanza efficiente usare le mappe hash.

codice più breve che mi viene in mente (e che utilizza HashMaps) sarà simile:

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

Ciò che può essere utilizzato come segue:

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

e genera in uscita come previsto:

cat

cane