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.

?

思路1.

對每一個數字都與其后序的數字進行比較，如果相同則返回true，如果不同，則指導遍歷完最后一個數字返回false，時間復雜度為(n-1)+(n-2)+....2+1,所以是O(n²)，代碼就不寫了，這方法不好。

思路2.

先排序，然后在遍歷vector，如果有相鄰的值相同，則返回true,負責將pivot設置為當前的值。總的時間復雜度為排序O(nlogn)+遍歷O(n)

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

　　

思路3，利用額外空間，unordered_map,如果元素不存在，計數器的值加1，如果存在，則返回true

class Solution { public:bool containsDuplicate(vector<int>& nums) {unordered_map<int,int> cmpMap;for( int i = 0; i < nums.size(); i++ ){if( cmpMap.find(nums[i]) == cmpMap.end() ){cmpMap[nums[i]]++;}else{return true;}}return false;} };

思路3我本來以為時間復雜度應該在O(n)但提交以后，速度還沒思路2的快，不知道是什么原因。

轉載于:https://www.cnblogs.com/rockwall/p/5744246.html

總結

以上是生活随笔為你收集整理的LeetCode【217. Contains Duplicate】的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。