Trier et liste toutes les occurrences dans un tableau de chaînes

Question

que je fais un peu d'exercice de codage et venir à travers cette question sur le tri d'un tableau de chaînes et la liste de toutes les occurrences de chaque chaîne unique dans le tableau. J'ai essayé de savoir si je peux le faire mieux que O (n), mais sans chance. Est-ce que quelqu'un a un bon échantillon pour ce problème?

ENTRÉE:

str_array = ['opq', 'def', 'mno', 'abc', 'def', 'xyz', 'abc', 'mno', 'abc'] 

SORTIE:

'abc' : 3 
'def' : 2 
'mno' : 2 
'xyz' : 1 
'opq' : 1 

Answer 1

En Python, il est très facile

>>> str_array = ['opq', 'def', 'mno', 'abc', 'def', 'xyz', 'abc', 'mno', 'abc'] 
>>> from collections import Counter 
>>> Counter(str_array).most_common() 
[('abc', 3), ('def', 2), ('mno', 2), ('xyz', 1), ('opq', 1)] 

Answer 2

Aucun algorithme ne sera en mesure de le faire dans un meilleur temps que O (n) parce que vous devez regarder chaque élément dans le tableau au moins une fois (ce qui signifie essentiellement un minimum de n étapes).

En Java, vous pouvez utiliser un HashMap pour maintenir le compte pour chaque chaîne:

import java.util.HashMap; 

HashMap<String, Integer> counter; 

for(String s : str_array) 
{ 
    counter.put(s, counter.get(s) + 1); 
} 

Pour obtenir la sortie:

for(String s : counter.keySet()) 
{ 
    System.out.println(s + " : " + counter.get(s)); 
} 

Answer 3

Dans Ruby

str_array.group_by{|s| s}.tap{|h| h.each{|k, v| h[k] = v.length}} 

avec le résultat:

{ 
    "opq" => 1, 
    "def" => 2, 
    "mno" => 2, 
    "abc" => 3, 
    "xyz" => 1 
}