對字符串數組中的所有匹配項進行排序並列出

-2

我正在做一些編碼練習，並在排序字符串數組時遇到此問題，並列出數組中每個唯一字符串的所有匹配項。我一直在試圖找出能否比O（n）做得更好，但沒有運氣。有沒有人有這個問題的好樣本？對字符串數組中的所有匹配項進行排序並列出

輸入：

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

OUTPUT：

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

來源

2013-06-05 xbeta

有很多樣品解決方案，如果你谷歌他們。如果您有具體問題，我建議您指定一種感興趣的語言。 –

你怎麼可能比O（n）做得更好？ –

你會如何比「O（n）」更快地瀏覽所有元素？ – Keppil

在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)]

來源

2013-06-05 05:54:48

這是正確的，除了打破O（n）來計算未排序列表中的元素的基本不可能性之外，注意'Counter'對於Python 2.7是新的。在此之前，您必須使用字典並自行增加計數 - 這並不複雜，但您必須更加明確。 –

沒有算法將能夠做到這一點比Ø更好的時間（n ），因爲你必須至少查看一次數組中的每個項目（這基本上意味着至少有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)); 
}

來源

2013-06-05 05:59:24

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

來源

2013-06-05 06:07:26 sawa

對字符串數組中的所有匹配項進行排序並列出

回答

相關問題