根据你的需要，可能有很多方法可以做到这一点。

#include <algorithm>
#include <iostream>
#include <random>
#include <vector>

int main() {
    // a seeded random number generator
    std::mt19937 prng(std::random_device{}());

    std::vector<int> vec {3, 4, 2, 1, 1, 3, 1};

    // get the min iterator to the first minimum element:
    auto mit = std::min_element(vec.begin(), vec.end());

    // collect the indices of all elements equal to the min element:
    std::vector<std::size_t> ids;
    for(auto fit = mit; fit != vec.end(); fit = std::find(fit + 1, vec.end(), *mit))
    {
        ids.push_back(std::distance(vec.begin(), fit));
    }

    // a distribution to select one of the indices in `ids`:
    std::uniform_int_distribution<std::size_t> dist(0, ids.size()-1);
    
    // print 10 randomly selected indices
    for(int i = 0; i < 10; ++i) {
        std::cout << ids[dist(prng)] << '\n';
    }
}

Demo

下面是一个基于选择采样的单遍变体（尽管它可能会做得更好），本质上是Reservoir Sampling的一个例子，样本大小为1。

#include <iostream>
#include <random>
#include <vector>
#include <iterator>

template <typename T, typename URBG>
T rmin(T first, T last, URBG &g) {
    if (first == last) return first;
    T min = first;

    using ud = std::uniform_int_distribution<std::size_t>;
    using param_type = ud::param_type;
    ud d;

    std::size_t mincnt = 1;
    ++first;
    while (first != last) {
        if (*first < *min) {
            /* Found new minimum. */
            min = first;
            mincnt = 1;
        } else if (*first == *min) {
            /* If equal to the minimum, select this with probability 1/mincnt + 1.
             * Second has 1/2 chance to be selected, third has 1/3, etc. */
            auto k = d(g, param_type{0, mincnt++});
            if (!k) {
                min = first;
            }
        }
        ++first;
    }

    return min;
}

int main() {
    // a seeded random number generator
    std::mt19937 prng(std::random_device{}());

    std::vector<int> vec{3, 4, 2, 1, 1, 3, 1};

    for (int i = 0; i < 10; i++) {
        auto it = rmin(vec.begin(), vec.end(), prng);
        std::cout << *it
                  << " is at a distance of: " << std::distance(vec.begin(), it)
                  << std::endl;
    }
}

Demo of the above

这个解决方案是随机的，但可能不会给所有的条目给予相等的概率，但是它避免了必须创建新的向量，并且仍然是O（N）。
它的工作原理是随机地将序列（在逻辑意义上）分成两部分，取其中的最小值，然后返回这两部分的最小值。
正如我所说，它可能不是均匀分布的，但它确实仍然是随机的。

#include <vector>
#include <algorithm>
#include <iostream>
#include <random>

template< typename T >
T minimum( T begin, T end ) {
    std::size_t size = std::distance( begin, end );
    if ( size<=1 ) return begin;

    std::random_device rd;  
    std::mt19937 gen(rd()); 
    std::uniform_int_distribution<size_t> ds(1,size-1);

    auto sep = begin + ds(gen);
    auto it1 = std::min_element(begin, sep );
    auto it2 = std::min_element(sep, end );
    if ( *it1<*it2 ) return it1;
    return it2;
}

int main() {
    std::vector<int> vec {3, 4, 2, 1, 1, 3, 1};
    for ( int j=0; j<10; ++j ) {
        auto it = minimum( vec.begin(), vec.end() );
        std::cout << *it << " is at a distance of: " << std::distance(vec.begin(), it) << std::endl;
    }
    return 0;
}

生产

Program returned: 0
1 is at a distance of: 4
1 is at a distance of: 3
1 is at a distance of: 6
1 is at a distance of: 3
1 is at a distance of: 6
1 is at a distance of: 3
1 is at a distance of: 4
1 is at a distance of: 3
1 is at a distance of: 3
1 is at a distance of: 6

神箭：https://godbolt.org/z/3EhzdGndz