对于重复元素返回 true

Question

我希望这个布尔函数在数组包含任何重复元素时返回 true，如果不包含任何重复元素则返回 false。我的代码是：-

bool containsDuplicate(vector<int>& nums) {
        int flag=0;
        for(int i=0;i<nums.size()/2;i++)
        {
            for(int j=1;j<nums.size();j++)
            {
                if(nums[i]==nums[j])
                {
                    flag=1;
                }
            }
        }
    if(flag==1)
        return true;
    else
        return false;
    
    }

它适用于包含重复项的数组，但在数组具有唯一元素的情况下不会返回 false。

Answer 1

您的解决方案具有时间复杂度O(n^2)。对于小数据来说它会很好，但对于较大的数据集来说它会很慢。

额外的数据结构可以大大提高速度：

bool containsDuplicate(const vector<int>& nums) {
    std::unordered_set<int> seen;
    for (auto x : nums) {
        if (!seen.insert(x).second) return false;
    }
    return true;
}

std::unordered_set<Key,Hash,KeyEqual,Allocator>::insert - cppreference.com

返回值

1-2) 返回一个对，其中包含一个指向插入元素（或阻止插入的元素）的迭代器和一个表示插入是否发生的布尔值。

由于插入std::unordered_set有O(1)时间复杂度，因此该解决方案的总时间复杂度为O(n)。性能狂人可以添加任意常量，该常量将根据数据大小确定使用哪种算法（如上所述，您的方法非常适合小数据）。