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

Question

给定一个矩阵，很容易计算出最小值的值和索引:

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

不过，我还想恢复第二个最小值(最大值同上)。

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

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

   优点:然后我可以恢复第二个、第三个... n 最小值

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

2. 找到 A 的最小位置后，我可以用一个较大的值(例如:Inf)替换该值，然后再次运行 min。

   优点:比排序便宜

   缺点:我必须修改矩阵(并将修改后的值保存在 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

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

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

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

希望对您有所帮助!