c++ - 当有多个最大值且最大值个数已知时，均匀分布数组中最大值的索引

Question

这是我看到的一道面试题，没有很好的解法。
问题的第一部分是:
给定一个整数 vector ，找到最大值的索引。但是，如果有多个最大值 - 您希望最大值的每个索引都有相同的概率被选择。

例如:如果我们有 vector (0,1,2,2,2,2) ，那么索引 2 被选中的概率为 0.25(索引 3 也是如此， 4,5).

你可以像这样用 C++ 解决它:

#include <iostream>
#include <bits/stdc++.h> 
using namespace std;

int getIndex(const vector<int>& numbers) {
  int maxNum = numeric_limits<int>::min();
  size_t idx = -1;
  size_t maxNumCtr = 0;

  for(size_t i = 0; i<numbers.size(); ++i) {
    int num = numbers[i];
    if(num > maxNum) {
      idx = i;
      maxNum = num;
      maxNumCtr = 1;
    } else if (num == maxNum) {
      maxNumCtr ++;
      idx = ((rand() % maxNumCtr) == 0) ? i : idx; 
    }
  }
  return idx;
} 

第二部分是:
现在你有一个额外的函数参数，它指示 vector 中最大值的出现次数。尝试改进您编写的算法的运行时间。

我的想法是，您可以在函数开始时仅计算一次 rand() 以找到均匀分布的最大索引，并使用一些计数器变量来了解何时获得正确的最大值循环中的索引。但这并没有改善运行时间，因为 rand 在 O(1) 中运行。

有更好的主意吗？

Answer 1

仅仅因为某些事物具有相同的大 O 复杂性并不意味着它具有相同的运行时。面试要求的是常数因子的变化，而不是复杂度的提高。

这是我在没有计数的情况下的做法

// Undefined if first == last
template<typename ForwardIterator, typename URBG>
int getIndex(ForwardIterator first, ForwardIterator last, URBG&& gen)
{
    int max = *std::max_element(first, last);
    std::vector<double> weights;
    std::transform(numbers.begin(), numbers.end(), std::back_inserter(weights), [max](int i){ return i == max; });
    // or auto weights = numbers | ranges::view::transform([max](int i){ return i == max; });

    std::discrete_distribution<int> dis(weights.begin(), weights.end());
    return dis(gen);
}

对数据进行 2 次传递，并构造一个相同大小的 std::discrete_distribution

如果您已经知道要从中挑选多少，则可以一次完成并使用 std::uniform_int_distribution

// Undefined if first == last
template<typename ForwardIterator, typename URBG>
int getIndex(ForwardIterator first, ForwardIterator last, size_t max_count, URBG&& gen)
{
    std::uniform_int_distribution<> dis(1, max_count);
    std::size_t nth = dis(gen);

    ForwardIterator best = first;
    std::size_t nth_best = nth;

    for (ForwardIterator it = first; it != last; ++it)
    {
        if (*best < *it)
        {
            // new max
            best = it;
            nth_best = nth;
        }
        else if (*it < *best) {} // nothing
        else if ((--nth_best) == 0) 
        {
            // found nth of this value
            best = it;
        }
    }

    return std::distance(first, best);
}