matlab - 在 Matlab 中找到第 m 个最小的数？

Question

有没有一种有效的方法可以在 Matlab 中找到长度为 n 的向量中的第 m 个最小数字？我必须使用 sort() 函数吗？谢谢并恭祝安康！

Answer 1

您无需对数字列表进行排序即可找到第m^个最小的数字。第m^个最小的数可以在线性时间内找到。即如果您的数组中有n元素，您可以O(n)通过使用选择算法和中位数算法的中位数及时得到解决方案。

链接是维基百科的文章，

http://en.wikipedia.org/wiki/Selection_algorithm#Linear_general_selection_algorithm_-_Median_of_Medians_algorithm

Answer 2

Edit 2: As Eitan pointed the first part of the answer doesn't address the question of finding the smallest m-th value but regarding the m-th element after the min value. The rest of the answer remains... +1 for Eitan's sharpness. While sort is probably very efficient to begin with, you can try to see whether a find will be better. For example:

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

the function find has added functionality that lets you find the 'first' or 'last' elements that meet some criterion. For example, if you want to find the first n elements in array X less than a value y, use find(X<y,n,'first')

This operation stops as soon as the first element meeting the condition is encountered, which can result in significant time savings if the array is large and the value you find happens to be far from the end.

I'd also like to recap what @woodchips said already in this SO discussion that is somewhat relevant to your question:

The best way to speed up basic built-in algorithms such as sort is to get a faster hardware. It will speed everything else up too. MATLAB is already doing that in an efficient manner, using an optimized code internally. Saying this, maybe a GPU add-on can improve this too...

Edit: For what it's worth, adding to Muster's comment, there is a FEX file called nth_element that is a MEX wrap of C++ that will get a solution in O(n) time for what you need. (similar to what @DDD pointed to)

Answer 3

As alternative solution, you may follow this way:

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

I hope this helps.