LeetCode217. Contains Duplicate解题

大家好，我又回来了，隔了一个星期没有刷题了 在这一个星期我想了很多，Java虽然上手容易，用着也很顺手，我目前最熟悉的也还是Java，但是Java语言的设计局限了它不能做很底层的东西，它实用性很强，但是LeetCode是偏向算法的，基础的东西，我觉得还是C++比较方便，也比较考验能力，因此我决定使用C++来解题

先来看一下题目

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.

题目大意是：给定一个int型的数组，你需要找出它是否有冗余的元素，如果有冗余的元素就返回TRUE，没有冗余的元素就返回FALSE。 冗余就是在数组中出现次数大于等于两次的元素。

解题思路

笨的方法是像选择排序那样逐个逐个比较，但是这种方法不可取，太慢。一定要争取只遍历一次。所以我想到了哈希表，第一次用C++刷LeetCode，我搜索了好半天文档，才搞明白了C++哈希表的使用。大致思路就是：在遍历的同时判断当前元素有没有在哈希表里,如果没有，就将当前元素值作为key加入哈希表，value就设为1好了，注意，要将数组元素作为key加入哈希表，寻找的时候就搜有没有这个key就好了。 下面上代码：

using namespace std;
class Solution {
public:
    bool containsDuplicate(vector<int>& nums) {
        unordered_map <int,int> mymap;
        for(int i=0;iif(mymap.count(nums[i])==1){
                return true;
            }else{
                mymap[nums[i]]=1;
            }
        }
        return false;
    }
};

更好的算法

AC之后我去寻找了一下排名比较靠前的算法，我很惊讶地发现，它们都用了sort(),对数组进行了排序，然后再遍历看当前元素的前后有没有相同的元素，有则判定为冗余。我很惊讶排序的用时竟然要比我用哈希表的用时还要短，后来想了想也是，我虽然是一次遍历，但是每个元素我都需要查找哈希表，即使哈希表访问任何元素的用时是常量，但是访问的次数非常多，因此耗时增加了。

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