c# - 获得最小第 N 个元素的有效方法

Question

给定一个字符串，有什么有效的方法可以

• 返回其中的第 N 个最低字符（ASCII 方式）？
• 返回第 N 个 lowset char* s * 吗？

我曾想过使用插入排序对 N 次迭代进行排序，或者对快速排序进行排序，其中枢轴位于第 N 个位置，但我在分析时间复杂度时遇到了问题。还有其他更有效的方法吗？

解决方案是什么，它不是一个字符串，而是一个小数列表？

Answer 1

如果您的字符串是 ASCII，您可以使用计数排序样式算法来完成。创建一个包含 256 个计数器的数组，遍历字符串，并为在字符串中找到的每个字符的代码增加一个计数器。现在从零开始遍历数组，累积到目前为止您看到的计数。当为字符添加计数器ch导致您的累积结果交叉时，如果字符串已排序N，您知道这ch是第- 个字符。n该算法是O(N)，其中N是字符串中的字符数。这是构建计数数组所需的时间。