在Matlab中找到第m小的数？

Question

有没有在Matlab中以高效的方式查找长度为n的向量中第m小的数？我是否必须使用sort()函数？谢谢和问候！

- Tim

---

请查看Matlab文件交换中的KTHVALUE：http://www.mathworks.com/matlabcentral/fileexchange/23195。还请参阅最小/最大选择：http://www.mathworks.com/matlabcentral/fileexchange/23576。 - H.Muster

这不是查找所有n个最小元素的重复任务。那项任务几乎总是需要进行排序才能高效完成，但此任务可以按下面的答案在线性时间内完成。 - Pieter Geerkens

Answer 1

你不需要对数字列表进行排序来找到第m^th小的数字。可以在线性时间内找到第m^th小的数字。也就是说，如果你的数组中有n个元素，你可以使用选择算法和中位数算法，在O(n)时间内得到一个解决方案。

链接指向维基百科文章：http://en.wikipedia.org/wiki/Selection_algorithm#Linear_general_selection_algorithm_-_Median_of_Medians_algorithm

- Deepu

Answer 2

编辑 2: 正如 Eitan 指出的那样，答案的第一部分并没有解决寻找最小 m-th 值的问题，而是关于最小值之后的第 m 个元素。其余部分的答案仍然有效...为 Eitan 的敏锐给予 +1。 虽然 sort 可能已经非常高效了，但你可以尝试看看是否可以使用 find 更好。例如：

id=find(X>min(X),m,'first');
id(end) % is the index of the smallest m-th element in X

函数find添加了功能，可以让你找到符合某些条件的“第一个”或“最后一个”元素。例如，如果你想找出数组X中小于值y的前n个元素，使用find(X<y,n,'first')。

一旦遇到满足条件的第一个元素，该操作就会停止，如果数组很大且要查找的值离末尾很远，则可以节省大量时间。

此外，在这个SO讨论中，@woodchips已经讲述了与你的问题有关的一些内容：

提高基本内置算法（如排序）速度的最佳方法是使用更快的硬件。这也会加快其他所有东西的速度。MATLAB已经在内部使用优化代码以有效地实现这一点。话虽如此，可能GPU插件也可以改善这一点... 编辑： 值得一提的是，除Muster的评论外，还有一个叫做nth_element的FEX文件，它是C++的MEX包装器，可以在O(n)时间内得到你需要的解决方案。（与@DDD指出的类似）

- bla

---

这个函数找到第一个_m_个大于最小值的数字的索引，但它们不一定包括第_m_个最小的数字，这可能与问题所要求的不同（也许我误解了问题？） - Eitan T

好的，在我的回答中，id(end) 是 X 中第 m 小元素的索引。我假设从那里获取值 X(id(end)) 是显而易见的。 - bla

这不是我想表达的意思。我的意思是X中第_m_个大于min(X)的值不一定是X中第_m_小的数字。例如，取m = 2和X = [9 9 1 2]。你的解决方案得出的结果是9，而我认为正确答案是2。 - Eitan T

我现在明白你的意思了...嗯，是的，我把索引和值搞混了。我很快就会编辑我的答案。谢谢Eitan。 - bla

Answer 3

作为替代方案，您可以按照以下方式进行：

A = randi(100,4000,1);
A = sort(A,'ascend');
m = 5; % the 5 smallest numbers in array A
B = A(1:5);

我希望这能帮到你。

- fpe

---

OP正在寻找此方法的替代方案。 - Gunther Struyf

@GuntherStruyf: OP问道：“我必须使用sort吗？”这并不直接意味着有其他方法。 - fpe

我认为这意味着他已经知道如何使用排序，而这本来就很简单。 - Gunther Struyf