C ++中未排序数组中缺少元素

Question

任何人都可以向我解释 STL C++ 中无序集合的逻辑，因为我是这个概念的新手。

他们如何使用无序集打印数组中缺少的元素。

这种方法是否有效，或者有任何其他方法比这种方法更有效。

逻辑如下：

for (int x = low; x <= high; x++)
      if (s.find(x) == s.end())
          cout << x << " ";

完整代码：

#include<iostream>
#include<vector>
#include<algorithm>
#include <unordered_set>
using namespace std;

void printMissing(int arr[], int n, int low,int high)
{

    unordered_set<int> s;
    for (int i = 0; i < n; i++)
        s.insert(arr[i]);
 
    // Traverse throught the range an print all
    // missing elements
    for (int x = low; x <= high; x++)
        if (s.find(x) == s.end())
            cout << x << " ";
}
 

int main()
{
    int arr[] = { 1, 3, 5, 4, 2, 8, 7 };
    int n = sizeof(arr) / sizeof(arr[0]);
    int low = 1, high = 10;
    printMissing(arr, n, low, high);
    return 0;
}

Answer 1

在一般情况下，这可能是最有效的方法。

unordered_set insert 和 find 的平均时间 恒定时间 复杂度，因此您可以存储元素之前在第一个 for 循环中快速看过，然后遍历整个范围并快速检查你是否看过它们。

作为恒定时间复杂度含义的示例，让我们展示一个 not 具有恒定时间复杂度的示例：

    // Traverse throught the range an print all
    // missing elements
    for (int x = low; x <= high; x++) {
        bool found = false;

        for (int i = 0; i < n; ++i) {
            // if one of the elements in the array matches this x we can
            // break out since the element does exist in arr
            if (arr[i] == x) {
                found = true;
                break;
            }
        }

        // was the element found? If not print it out
        if (!found) cout << x << " ";

    }

对于 low, high 范围内的每个元素，如果该元素不存在，我们必须遍历 full 数组（对于大型输入数组）。运行此算法针对 low, high 范围内的单个元素所花费的时间与数组中的元素数量成线性比例关系，因此我们将此称为线性查找时间。

当数组相对较大时，常量查找时间通常会超过线性查找时间。

C ++中未排序数组中缺少元素

Missing elements in unsorted array in C++

c++

arrays

c++14

hashtable

unordered-set