CodeSignal：C++ 超出了执行时间限制

Question

我正在尝试先解决编程问题Duplicate on codesignal。问题是“给定一个仅包含 1 到 a.length 范围内的数字的数组 a，找到第一个重复数字，其中第二次出现的索引最小”。

示例：对于 a = [2, 1, 3, 5, 3, 2]，输出应为 firstDuplicate(a) = 3

有 2 个重复项：数字 2 和 3。第二次出现的 3 的索引比第二次出现的 2 的索引小，因此答案是 3。

使用这段代码，我通过了 21/23 次测试，但随后它告诉我该程序超过了测试 22 的执行时间限制。我将如何让它更快以通过剩余的两个测试？

#include <algorithm>

int firstDuplicate(vector<int> a) {
    vector<int> seen;
    
    for (size_t i = 0; i < a.size(); ++i){
        if (std::find(seen.begin(), seen.end(), a[i]) != seen.end()){
            return a[i];
        }else{
            seen.push_back(a[i]);
        }
    }
    
    if (seen == a){
        return -1;
    }
    
}

Answer 1

std::find 是容器中第一个元素和最后一个元素之间的距离（或直到找到数字）的线性时间复杂度，因此最坏情况下的复杂度为 O(N)，因此您的算法将是 O(N^2).

与其将你的数字存储在一个向量中并每次都搜索它，Yyu 应该使用 std::map 进行散列来存储遇到的数字，如果迭代时 return 一个数字，它已存在于地图中。

std::map<int, int> hash;
for(const auto &i: a) {
    if(hash[i])
        return i;
    else
        hash[i] = 1;
}

编辑：如果键的顺序无关紧要，std::unordered_map 甚至更有效，因为与 std::map 的对数插入复杂度相比，插入时间复杂度在平均情况下是恒定的。

Answer 2

每当您被问到有关“查找重复项”、“查找丢失的元素”或“查找应该存在的东西”的问题时，您的第一直觉应该是使用散列table。在 C++ 中，有 unordered_map 和 unordered_set 类用于此类编码练习。 unordered_set 实际上是键到布尔值的映射。

此外，通过引用而不是值向您传递矢量。按值传递会产生复制整个向量的开销。

此外，这种比较最终似乎代价高昂且不必要。

这可能更接近您想要的：

#include <unordered_set>


int firstDuplicate(const vector<int>& a) {
    std::unordered_set<int> seen;
    
    for (int i : a) {
       auto result_pair = seen.insert(i);
       bool duplicate = (result_pair.second == false);
       if (duplicate) {
          return (i);
       }
    }

    return -1;
   
}

Answer 3

这可能是一个不必要的优化，但我想我会尝试稍微更好地利用规范。散列 table 主要用于从可能的键到实际键的转换相当稀疏的情况——也就是说，只使用了一小部分可能的键。例如，如果您的密钥是长度最多为 20 个字符的字符串，则理论上最大密钥数为 256²⁰。有了那么多可能的键，很明显没有实际的程序会存储超过一个极小的百分比，所以散列 table 是有意义的。

然而，在这种情况下，我们被告知输入是：“仅包含 1 到 a.length 范围内的数字的数组 a”。因此，即使有一半的数字是重复的，我们也会使用 50% 的可能键。

在这种情况下，我会使用 std::vector<bool> 而不是散列 table，尽管它经常受到诽谤，并且希望在绝大多数情况下获得更好的性能。

int firstDuplicate(std::vector<int> const &input) { 
    std::vector<bool> seen(input.size()+1);

    for (auto i : input) { 
        if (seen[i])
            return i;
        seen[i] = true;
    }
    return -1;
}

这里的优势相当简单：至少在典型情况下，std::vector<bool> 使用特化来将 bool 存储在每个位中。通过这种方式，我们只为每个输入数量存储一位，从而增加了存储密度，因此我们可以期待对缓存的出色使用。特别是，只要缓存中的字节数至少比输入数组中元素数的 1/8^th 多一点，我们就可以期望所有 seen 大部分时间都在缓存中。

请不要误会：如果您环顾四周，您会发现很多文章指出 vector<bool> 存在问题——在某些情况下，这完全正确。有些地方和时间应该避免vector<bool>。但是 none 它的局限性适用于我们在这里使用它的方式——它确实在存储密度方面提供了一个非常有用的优势，尤其是对于这种情况。

我们还可以编写一些自定义代码来实现位图，从而提供比 vector<bool> 更快的代码。但是使用 vector<bool> 很容易，编写我们自己的更高效的替代品是相当多的额外工作...

CodeSignal：C++ 超出了执行时间限制

CodeSignal: Execution time limit exceeded with c++

c++

execution-time