c++ - std::unordered_set::find() 函数比 std::find() 快吗？

Question

我正在研究 LeetCode 的“第一个缺失的积极”解决方案

https://leetcode.com/problems/first-missing-positive/submissions/

第一个解决方案是（171 个测试用例的 471 毫秒）：

#include <unordered_set>
class Solution {
public:
        
    int firstMissingPositive(vector<int>& nums) {
        std::unordered_set<int> s;
        for (auto& n: nums)
            if (n > 0)
                s.insert(n);
        int ret = 1;
        while (s.find(ret) != s.end())
            ret++;
        
        return ret;
    }
};

我还测试了一个更简单的解决方案，其中不将数字添加到集合中，而是只搜索 std::vector。此解决方案超出时间限制

class Solution {
public:
   
    int firstMissingPositive(vector<int>& nums) {

        int ret = 1; 
        while(std::find(nums.begin(), nums.end(), ret) != nums.end())
            ret ++;
                       
        return ret;
    }
};

奇怪的是，当我取出if (n > 0)第一个解决方案中的条件时，每次都对整个集合进行排序时，它并没有超过时间限制，相反，结果运行时间实际上提高到了 394ms

#include <unordered_set>
class Solution {
public:
        
    int firstMissingPositive(vector<int>& nums) {
        std::unordered_set<int> s;
        for (auto& n: nums)
            s.insert(n);
        int ret = 1;
        while (s.find(ret) != s.end())
            ret++;
        
        return ret;
    }
};

为什么将向量元素添加到一个std::unordered_set然后循环使用s.find比简单地使用std::find()函数循环遍历数组更快？

标签： c++unordered-set