求最小N个元素的有效方法
求最小N个元素的有效方法
提问于 2013-01-20 21:35:53
给定一个字符串，有什么有效的方法
- 返回N个最低的炭(ASCII wise)？
- 返回N个低设置的字符**在其中？
我曾经想过用插入排序排序N个迭代，或者排序快速排序，其中枢轴位于N个位置，但我在分析时间复杂性时遇到了问题。还有其他更有效的方法吗？
解决办法是，它不是字符串，而是小数列表？
回答 1
Stack Overflow用户
回答已采纳
发布于 2013-01-20 21:42:12
如果您的字符串是ASCII，则可以使用计数-排序样式的算法来完成它。创建一个由256个计数器组成的数组，遍历该字符串，并为您在字符串中找到的每个字符的代码增加一个计数器。现在，从零开始遍历数组，积累到目前为止所见的计数。当为字符ch添加计数器时，将导致您的累积结果与N交叉，如果对字符串进行排序，您将知道ch是n-th字符。这个算法是O(N)，其中N是字符串中的字符数。这是构建计数数组所需的时间。
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/14429609
复制相关文章
相似问题
腾讯云开发者
