C++ STL unordered_set实现无序数组缺失元素查询的逻辑与效率疑问

unordered_set是STL提供的基于哈希表实现的无序集合，核心特性是：存储的元素无重复，平均情况下插入、查找元素的时间复杂度都是O(1)。
这段代码的执行逻辑分为两步：

• 第一步遍历输入数组的所有元素，全部插入unordered_set中，自动完成去重
• 第二步就是你贴的核心循环：逐个遍历[low, high]区间内的所有整数x：
  调用s.find(x)查找x是否在集合中，如果返回迭代器等于s.end()，说明x没有出现在原数组中，属于缺失元素，直接打印输出。

以你给出的示例为例：原数组元素为[1,3,5,4,2,8,7]，插入到集合后包含的元素就是1_8，遍历110时，9、10查找失败，所以最终输出结果为9 10。

当前方案的效率 #

• 平均时间复杂度：O(n + L)，其中n是原数组长度，L = high - low + 1是区间长度。插入n个元素平均耗时O(n)，遍历区间的L次查找每次平均O(1)。
• 缺点：哈希表有额外的内存开销，存在哈希碰撞的最坏情况，最坏情况查找复杂度退化到O(n)，整体耗时会变成O(n*L)；如果区间长度L特别大（比如到1e9级别），遍历整个区间完全不可行。

更高效的实现方案 #

根据场景不同有两种更优选择：

场景A：区间长度L不大（比如小于1e6） #

用布尔数组替代unordered_set，完全规避哈希开销，运行速度更快，内存更紧凑：

void printMissing(int arr[], int n, int low,int high) {
    int range = high - low + 1;
    vector<bool> exist(range, false);
    for (int i = 0; i < n; i++) {
        // 只标记在区间内的元素
        if (arr[i] >= low && arr[i] <= high) {
            exist[arr[i] - low] = true;
        }
    }
    for (int i = 0; i < range; i++) {
        if (!exist[i]) cout << low + i << " ";
    }
}

场景B：区间长度L远大于数组长度n #

对原数组排序后直接遍历找空缺，时间复杂度仅和数组长度相关，不受区间大小影响：

void printMissing(int arr[], int n, int low,int high) {
    sort(arr, arr + n);
    int cur = low;
    for (int i = 0; i < n && cur <= high; i++) {
        // 跳过小于当前待检查值的重复/无效元素
        if (arr[i] < cur) continue;
        // 中间有空缺，全部是缺失元素
        if (arr[i] > cur) {
            while (cur < arr[i] && cur <= high) {
                cout << cur << " ";
                cur++;
            }
        }
        cur = arr[i] + 1;
    }
    // 输出数组最大值之后的剩余缺失元素
    while (cur <= high) {
        cout << cur << " ";
        cur++;
    }
}

这个方案的时间复杂度是O(n log n)，当区间长度L远大于n*log n的时候，效率远高于前两种方案。

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