有效的方式來獲得最小的n個元素（一個或多個）

給定一個字符串，多麼有效的方法是那裏有效的方式來獲得最小的n個元素（一個或多個）

收益在它的N個最低字符（ASCII明智的）？
返回第N個低位字符* s *在裏面？

我想過使用插入排序或排序快速排序N迭代，其中樞軸位於第N個位置，但我有分析時間複雜性的問題。還有其他更有效的方法嗎？

解決方案是什麼？它不是一個字符串，而是一個小數列表？

來源

2013-01-20 Elad Benda

如果我理解正確，請查看[quickselect]（http://en.wikipedia.org/wiki/Quickselect）。 – svick

超。解決方案是什麼？它不是一個字符串，而是一個小數列表？ –

我投票重新提出這個問題：我認爲這是一個關於在小數字中應用統計算法的合法問題;它根本不是「過於本地化」。 – dasblinkenlight

如果你的字符串是ASCII碼，你可以使用counting-sort樣式算法。製作256個計數器數組，檢查字符串，併爲您在字符串中找到的每個字符代碼增加一個計數器。現在從零開始數組，累計迄今爲止看到的計數。當爲字符ch添加計數器會導致您的累計結果跨越N時，如果字符串已排序，則知道ch是第n個字符。該算法是O(N)，其中N是字符串中的字符數。這是建立計數數組所需的時間。

來源

2013-01-20 21:42:12 dasblinkenlight

超。解決方案是什麼？它不是一個字符串，而是一個小數列表？ –

@EladBenda如果你在小數點處有'K'，你可以在時間和內存中使用相同的簡單算法來處理'O（K）'複雜性，或者選擇[廣義選擇（中值中值）算法]（ http://en.wikipedia.org/wiki/Selection_algorithm#Linear_general_selection_algorithm_-_Median_of_Medians_algorithm），這是相當複雜的。 – dasblinkenlight

如果小數不在'K'範圍內，該怎麼辦？ –

有效的方式來獲得最小的n個元素（一個或多個）

回答

相關問題