Сортировка и список всех вхождений в строковом массиве

Question

Я выполняю некоторые упражнения по кодированию и сталкиваюсь с этим вопросом при сортировке строкового массива и перечисляю все вхождения каждой уникальной строки в массиве. Я пытался выяснить, могу ли я сделать это лучше, чем O (n), но без везения. У кого-нибудь есть хороший образец для этой проблемы?

ВХОД:

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

ВЫВОД:

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

Answer 1

В Python очень легко

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

алгоритм не будет в состоянии сделать это в лучшее время, чем O (п), потому что вы должны смотреть на каждый элемент в массиве хотя бы один раз (что в основном означает минимум n шагов).

В Java вы можете использовать HashMap, чтобы сохранить количество для каждой строки:

import java.util.HashMap; 

HashMap<String, Integer> counter; 

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

Чтобы получить выход:

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

Answer 3

В Ruby

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

с результатом:

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