217. Contains Duplicate

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.

Example 1:

Input: [1,2,3,1]
Output: true

Example 2:

Input: [1,2,3,4]
Output: false

Example 3:

Input: [1,1,1,3,3,4,3,2,4,2]
Output: true

algorithm thought

判断是否有重复数组，O(n)的解法就是使用一个hash table保存之前出现的值，如果出现重复的，就return。

还有一种方法是我做完O(n)解法之后，发现有人用O(nlgn)的排序解法做出来的，竟然还快一点。首先排序数组，然后判断连续的index是否有重复的数字。

唯一可能的解释，排序算法比O(n)算法快的理由就是，n不大，lgn小于O(n)解法前面的系数。

code

class Solution {
public:
    bool containsDuplicate(vector<int>& nums) {
        // O(n) version
        // unordered_set<int> se(nums.size());
        // for(auto&num:nums){
        //     if(se.count(num))
        //         return true;
        //     se.insert(num);
        // }
        // return false;
        // the next is sort version
        if(nums.size()<2)
            return false;
        sort(nums.begin(),nums.end());
        for(int i=0;i<nums.size()-1;++i){
            if(nums[i]==nums[i+1])
                return true;
        }
        return false;
    }
};

algorithm analysis

对于O(n)的算法，开始定义set的时候，要给他分配n的空间。因为STL里的alloc是动态递增空间的。如果空间不够，会重新开辟空间。所以提前分配好n的空间，能减少算法运行的时间和空间。