LeetCode 217 Contains Duplicate（包含重復數字）（Vector、hash）

翻譯

給定一個整型數字數組，找出這個數組是否包含任何重復內容。

如果任何值出現了至少兩次，那麼返回真（true），

如果每個值都是互不相同的，那麼返回假（false）。

原文

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.

分析

這次的題意比較簡單，就不多闡述了。

我的第一反應還是比較原始的（我盡量在每次解題過程中描述我的思考過程），用std::find()函數在vector中查找是否有重復的值。

bool containsDuplicate(vector& nums) {
    vector::iterator temp;
    int num_to_find;
    for (vector::iterator index = nums.begin(); index < nums.end(); ++index) {
        num_to_find = *index;
        temp = std::find(index + 1, nums.end(), num_to_find);
        if (temp != nums.end())
            return true;
    }
    return false;
}

然後放到LeetCode上試了一試，結果是超時了，好吧，畢竟測試用例中都是多少萬級的數據。不急不急，如果用sort函數先排個序呢？

bool containsDuplicate(vector& nums) {
sort(nums.begin(), nums.end());
    vector::iterator temp;
    int num_to_find;
    for (vector::iterator index = nums.begin(); index < nums.end(); ++index) {
        num_to_find = *index;
        temp = std::find(index + 1, nums.end(), num_to_find);
        if (temp != nums.end())
            return true;
    }
    return false;
}

發現並沒有用，喔對了，即便排序了上面的代碼還是對後面的所有數據都進行了一次掃描判斷。

但是呢，既然排了序，直接用下一個數值和當前數值比較不就好了？

current == next  說明什麼？重復了呗！
current < next 說明什麼？我都排過序了啊，這不是妥妥的嘛？不用判斷這個了。
current > next 說明什麼？都說了已經排過序了，這可能嗎！

那麼，看代碼……（我把index改成了it，只是為了讓那一行顯得短一點，兩個變量的意義是一樣的）

bool containsDuplicate(vector& nums) {
    if (nums.size() <= 1)
        return false;
    sort(nums.begin(), nums.end());
    vector::iterator temp;
    int num_to_find;
    for (vector::iterator it = nums.begin(), temp = it + 1; it < nums.end(); ++it,++temp) {
        if (*temp == *it)   return true;
    }
    return false;
}

不過其實這裡出現了兩次temp：

temp = it + 1;
++ temp;

看起來還是比較麻煩的，還是改得清晰點：

bool containsDuplicate(vector& nums) {
    if (nums.size() <= 1)
        return false;
    sort(nums.begin(), nums.end());
    vector::iterator temp;
    int num_to_find;
    for (vector::iterator it = nums.begin(); it < nums.end(); ++it) {
        temp = it + 1;
        if (*temp == *it) return true;
    }
    return false;
}

代碼

class Solution {
public:
    bool containsDuplicate(vector& nums) {
        if (nums.size() <= 1)
            return false;
        sort(nums.begin(), nums.end());
        vector::iterator temp;
        int num_to_find;
        for (vector::iterator it = nums.begin(); it < nums.end(); ++it) {
            temp = it + 1;
            if (*temp == *it) return true;
        }
        return false;
    }
};

進階

我的代碼是44ms，來看看大神寫的36ms的是怎樣的吧，加油！

class Solution {
public:
    bool containsDuplicate(vector& nums) {
        if(nums.size() == 0)    return false;

        int min = nums[0], max = nums[0];
        for(auto n : nums){
            if(n > max)     max = n;
            if(n < min)    min = n;
        }

        int arr[max - min + 1] = {0};
        for(auto n : nums){
            ++arr[n - min];
        }

        for(int i = 0; i != (max - min + 1); ++i)
            if(arr[i] > 1)  return true;
        return false;
    }
};

有意思的是，我用sort函數來排序之後反而增加了4ms。

class Solution {
public:
    bool containsDuplicate(vector& nums) {
        if (nums.size() == 0)    return false;
        sort(nums.begin(), nums.end());
        int min = nums[0], max = nums[nums.size() - 1];

        int arr[max - min + 1] = { 0 };
        for (auto n : nums) {
            ++arr[n - min];
        }

        for (int i = 0; i != (max - min + 1); ++i)
            if (arr[i] > 1)  return true;
        return false;
    }
};

hash

class Solution {
public:
    bool containsDuplicate(vector& nums) {
        int count=1000;
        vector hash[count];
        for(int i=0;i=0?nums[i]:-nums[i])%count;
            for(int j=0;j