从含N个元素的数组提取M个不同随机值的O(M)算法可行吗？

O(M)时间复杂度是否可行？ #

完全不可行。核心原因在于：要完成这个任务，你首先必须确认原数组中唯一元素的总数K——如果K < M，任务根本无法完成。而要获取K的值，至少需要遍历整个数组一次（O(N)时间），这已经超出了O(M)的复杂度范畴。即便M远小于N，你也无法绕过“识别重复元素”或“确保选中元素不重复”的步骤，这必然需要至少O(N)的时间开销，不可能仅用O(M)时间完成。

最优时间复杂度是多少？ #

最优时间复杂度为O(N + M)，具体分为两个阶段：

• O(N)：遍历数组，要么收集所有唯一元素，要么在遍历过程中完成抽样；
• O(M)：从筛选出的唯一元素中随机选取M个不重复的元素。

如果采用“边遍历边抽样”的方式（无需提前收集全部唯一元素），平均时间开销会更接近O(N)，但最坏情况下仍为O(N)（比如数组前半部分全是重复元素，后半部分才出现新的唯一元素）。

示例代码 #

C++ 实现（先收集唯一元素再抽样） #

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

std::vector<int> extractUniqueRandom(const std::vector<int>& arr, int m) {
    // 收集所有唯一元素
    std::unordered_set<int> uniqueSet(arr.begin(), arr.end());
    if (uniqueSet.size() < static_cast<size_t>(m)) {
        throw std::invalid_argument("唯一元素数量不足M个");
    }

    // 转换为vector以便随机访问
    std::vector<int> uniqueVec(uniqueSet.begin(), uniqueSet.end());
    std::random_device rd;
    std::mt19937 gen(rd());

    // 使用Fisher-Yates洗牌的前M个元素作为结果，保证随机性
    for (int i = 0; i < m; ++i) {
        std::uniform_int_distribution<> dist(i, static_cast<int>(uniqueVec.size()) - 1);
        int swapIdx = dist(gen);
        std::swap(uniqueVec[i], uniqueVec[swapIdx]);
    }

    return std::vector<int>(uniqueVec.begin(), uniqueVec.begin() + m);
}

int main() {
    std::vector<int> arr = {2, 5, 2, 7, 5, 9, 1, 9};
    try {
        auto result = extractUniqueRandom(arr, 3);
        std::cout << "抽取的3个不同随机值：";
        for (int num : result) {
            std::cout << num << " ";
        }
        std::cout << "\n";
    } catch (const std::exception& e) {
        std::cerr << "错误：" << e.what() << "\n";
    }
    return 0;
}

Python 实现（边遍历边抽样，无需提前收集全部唯一元素） #

这个实现用了蓄水池抽样的变种，在遍历数组时动态选取唯一元素，无需提前统计所有唯一元素，适合处理超大数组的场景：

import random

def extract_unique_random(arr, m):
    selected = []
    seen = set()
    unique_count = 0

    for num in arr:
        if num not in seen:
            seen.add(num)
            unique_count += 1
            # 当选中的元素不足M个时，直接加入；否则以 M/unique_count 的概率替换已选中元素
            if len(selected) < m:
                selected.append(num)
            else:
                if random.random() < m / unique_count:
                    replace_idx = random.randint(0, m-1)
                    selected[replace_idx] = num

    if len(selected) < m:
        raise ValueError("唯一元素数量不足M个")
    return selected

# 测试示例
arr = [2, 5, 2, 7, 5, 9, 1, 9]
try:
    result = extract_unique_random(arr, 3)
    print("抽取的3个不同随机值：", result)
except ValueError as e:
    print("错误：", e)

内容的提问来源于stack exchange，提问作者Kaiyakha