对数组中的最大数量的索引进行采样,概率为1 /(最大数量的数量)

Question

这是我最近面临的一个面试问题.程序返回数组中最大数字的索引[注意:数组可能包含也可能不包含多个最大数字副本],这样每个索引(包含最大数字)的概率为1 /最大数字被退回.

例子:

• [-1 3 2 3 3],每个职位[1,3,4]的概率为1/3(三个3)
• [2 4 6 6 3 1 6 6],[2,3,6,7]中的每一个都有1/4的概率被返回(对应于6s的位置).

首先,我给出了O(n)时间和O(n)空间算法,我收集了最大索引集,然后从集合中返回一个随机数.但他要求O(n)时间和O(1)复杂度计划然后我想出了这个.

int find_maxIndex(vector<int> a)
{
     max = a[0];
     max_index = 0;
     count = 0;

     for(i = 1 to a.size())
     {
         if(max < a[i])
         {
             max = a[i];
             count = 0;
         }
         if(max == a[i])
         {
              count++;
              if(rand < 1/count) //rand = a random number in the range of [0,1]
                  max_index = i;
         }
      }
      return max_index;
}

我给了他这个解决方案.但我怀疑的是,这个程序是否会以相同的概率选择最大数的索引之一.希望我很清楚.有没有其他方法可以做到这一点？

Answer 1

你的算法工作得很好，你可以通过归纳来证明它。

也就是说，假设它适用于任何 size 的数组N，证明它适用于任何 size 的数组N+1。

因此，给定一个 size 的数组N+1，可以将其视为 size 的子数组N，后面跟着一个新元素。根据假设，您的算法统一选择子数组的最大元素之一......然后其行为如下：

如果新元素大于子数组的最大值，则返回该元素。这显然是正确的。

如果新元素小于子数组的最大值，则返回子数组的算法结果。也显然是正确的。

唯一稍微棘手的部分是当新元素等于子数组的最大元素时。在这种情况下，设子数组中最大元素的数量为k。然后，根据假设，您的算法以 概率 选择其中之一1/k。通过保留相同元素的概率k/(k+1)，您可以根据需要使选择相同元素的总体概率等于1/k* k /(k+1)== 1/(k+1)。您还以相同的概率选择最后一个元素，这样我们就完成了。

要完成归纳证明，只需验证算法是否适用于大小为 1 的数组。此外，为了实现质量目的，请修复它，以免在大小为零的数组上崩溃:-)

[更新]

顺便说一句，这个算法及其证明与Fisher-Yates 洗牌密切相关（我一直以为是“Knuth 洗牌算法”，但维基百科说我落伍了）。