contains-duplicate

Contains Duplicate – LeetCode 217

Problem

Description

Given an array of integers, find if the array contains any duplicates. Your function should return true if any value appears at least twice in the array, and it should return false if every element is distinct.

Answer

Original

Code

class Solution {
public:
    bool containsDuplicate(vector<int>& nums) {
        set<int> s_int;
        for(unsigned i = 0; i != nums.size(); ++i){
            if(s_int.count(nums[i]) == 0)
                s_int.insert(nums[i]);
            else
                return true;
        }
        return false;
    }
};

思路

使用Set存储出现过的，一旦发现重复就返回，性能开销有一部分被STL所消耗。时间复杂度$O(n)$，空间复杂度$O(n)$。
耗时$43$ ms，排名$73.04\%$

Better

思路

先进行排序再遍历。时间复杂度$O(nlog{n})$，空间复杂度$O(1)$。

Code

class Solution {
public:
    bool containsDuplicate(vector<int>& nums) {
        sort(nums.begin(),nums.end());
        for(int i = 1; i < nums.size(); ++i){
            if(nums[i] == nums[i-1]) return true;
        }
        return false;
    }
};