计算第二个最小值的有效方法

Question

给定矩阵,很容易计算最小值的值和索引:

A = rand(10);
[value, index] = min(A(:));

但是我还想恢复第二个最小值(最大值为idem).

我当然可以采用以下两种方法中的任何一种:

1. 将A转换为向量并对其进行排序.

   PROS:我可以恢复第二个,第三个...... n最小值

   缺点:如果A很大,排序很昂贵

2. 一旦找到A的最小位置,我可以将该值替换为大值(例如:Inf),然后min再次运行.

   PROS:比排序便宜

   缺点:我必须修改我的矩阵(并将修改后的值保存在aux变量中).在大型矩阵上重新运行min也很昂贵.

我想知道是否有更好的解决方案:

当计算min算法时必须跟踪到目前为止找到的最小值,直到新值具有较低的值(然后我们更新该值).相反,如果我们跟踪n到目前为止发现的最后一个最小值将允许恢复最小值n.

我可以实现这一点,但我想知道它是否是最好的方法,或者它是否已经实现.

Answer 1

我不知道在哪种情况下它会比排序便宜，但一种简单但不那么快的方法是使用以下代码。我可能是错的，但我不认为如果你只想要第一分钟和第二分钟，你可以使用内置函数变得更快。

A = rand(10);
[firstMin, firstMinIndex] = min(A(:));
secondMin = min(A(A~=firstMin));
secondMinIndex = find(A==secondMin); % slow, but use only if you need the index

在这里，您将遍历矩阵两次，一次用于布尔运算，另一次用于第二分钟。

在对 2000x2000 和 4000x4000 随机矩阵进行一些测试后，该代码片段似乎比应用于同一矩阵的排序函数快 3.5 倍左右。

如果您确实需要更高的效率，则必须编写自己的 mex 例程，理论上您可以通过 n+log n-2 比较获得两个值，如 @luismendotomas 提供的链接中所述。

希望这有帮助！