217. 存在重復(fù)元素
題目：
給你一個整數(shù)數(shù)組?nums?。如果任一值在數(shù)組中出現(xiàn)?至少兩次?，返回?true?；如果數(shù)組中每個元素互不相同，返回?false?。
示例 1：
輸入：nums = [1,2,3,1]
輸出：true
示例 2：
輸入：nums = [1,2,3,4]
輸出：false
示例?3：
輸入：nums = [1,1,1,3,3,4,3,2,4,2]
輸出：true
提示：
1 <= nums.length <= 10^5-10^9 <= nums[i] <= 10^9
代碼示例：
（1）
class Solution {
public:
? ? bool containsDuplicate(vector<int>& nums)
? ? {
? ? ? ? set<int>num1;
? ? ? ? for(auto x:nums)
? ? ? ? {
? ? ? ? ? ? num1.insert(x);
? ? ? ? }
? ? ? ? if(nums.size()==num1.size())
? ? ? ? {
? ? ? ? ? ? return 0;
? ? ? ? }
? ? ? ? return 1;
? ? }
};
第一時間想到的是用set容器的特性：不存在重復(fù)元素。把vector里面的每一個元素insert進(jìn)set容器中，然后比較set容器和原來的vector的長度，如果一樣長，則沒有重復(fù)元素，如果不一樣長，則有重復(fù)元素。
結(jié)果證明方法確實可行，但是因為時間復(fù)雜度大，提示中數(shù)據(jù)量很大導(dǎo)致花了很長時間，而且內(nèi)存占用高達(dá)七十兆，顯然是不太好的。
接下來就想辦法優(yōu)化一下算法
第二次的代碼如下：
class Solution {
public:
? ? bool containsDuplicate(vector<int>& nums)
? ? {
? ? ? ? sort(nums.begin(),nums.end());
? ? ? ? int x = nums.size();
? ? ? ? for(int i = 0;i<x-1;i++)
? ? ? ? {
? ? ? ? ? ? if(nums[i]==nums[i+1])
? ? ? ? ? ? {
? ? ? ? ? ? ? ? return 1;
? ? ? ? ? ? }
? ? ? ? }
? ? ? ? return 0;
? ? }
};
這一次利用sort函數(shù)，把vector的元素排好序，然后通過比較相鄰的元素是否相等來判斷是否存在相等的元素。這樣的好處在于代碼更簡潔，耗時以及內(nèi)存更小
