存在重復(fù)元素

力扣（LeetCode）

給定一個(gè)整數(shù)數(shù)組，判斷是否存在重復(fù)元素。
如果存在一值在數(shù)組中出現(xiàn)至少兩次，函數(shù)返回 true 。如果數(shù)組中每個(gè)元素都不相同，則返回 false 。

示例 1:
輸入: [1,2,3,1]
輸出: true

示例 2:
輸入: [1,2,3,4]
輸出: false

示例 3:
輸入: [1,1,1,3,3,4,3,2,4,2]
輸出: true

---

一般解法

雙重for循環(huán)，依次兩兩匹配是否相等

class Solution(object):def containsDuplicate(self, nums):""":type nums: List[int]:rtype: bool"""# 方法一for i in nums:for j in nums[nums.index(i)+1:len(nums)]:if i == j:return Truereturn False

時(shí)間復(fù)雜度：$O(N^2)$
空間復(fù)雜度：？

Python集合不重復(fù)性，將列表轉(zhuǎn)換為集合，以長度是否變化來判斷是否有重復(fù)數(shù)字

# 方法二：Python集合元素不重復(fù)性if len(set(nums)) != len(nums):return Truereturn False# 方法三：簡化方法二return len(set(nums)) != len(nums)

時(shí)間復(fù)雜度：$O(N)$，len()的時(shí)空復(fù)雜度都是$O(1)$，set()的時(shí)間復(fù)雜度為$O(N)$

set is actually a hashTable.
a list to set: Iterating over a list is $O(N)$, and adding each element to the hash set is $O(1)$, so the total operation is $O(N)$.

空間復(fù)雜度：$O(N)$ ？

注意：

Python中的True和False，首字母大寫！

使用方法一時(shí)，注意下標(biāo)越界、列表切片操作

---

力扣官方解法

方法一：排序

在對數(shù)字從小到大排序之后，數(shù)組的重復(fù)元素一定出現(xiàn)在相鄰位置中。因此，我們可以掃描已排序的數(shù)組，每次判斷相鄰的兩個(gè)元素是否相等，如果相等則說明存在重復(fù)的元素。

class Solution {public boolean containsDuplicate(int[] nums) {Arrays.sort(nums);int n = nums.length;for (int i = 0; i < n - 1; i++) {if (nums[i] == nums[i + 1]) {return true;}}return false;} }

復(fù)雜度分析

時(shí)間復(fù)雜度：O(N$logN$)，其中 N 為數(shù)組的長度。需要對數(shù)組進(jìn)行排序。Arrays.sort()排序算法的時(shí)間復(fù)雜度為O(N$logN$)

TODO 空間復(fù)雜度：O($logN$)，其中 N 為數(shù)組的長度。注意我們在這里應(yīng)當(dāng)考慮遞歸調(diào)用棧的深度。

java代碼轉(zhuǎn)python
注意：當(dāng)nums中只有一個(gè)元素如何處理！

class Solution(object):def containsDuplicate(self, nums):# 數(shù)組排序，原地操作nums.sort()if len(nums) != 0:for i in range(len(nums)-1):if nums[i] == nums[i+1]:return Truereturn Falsereturn False

方法二：哈希表

對于數(shù)組中每個(gè)元素，我們將它插入到哈希表中。如果插入一個(gè)元素時(shí)發(fā)現(xiàn)該元素已經(jīng)存在于哈希表中，則說明存在重復(fù)的元素。

HashSet集合：不允許存儲(chǔ)重復(fù)的元素，查詢速度快

// java class Solution {public boolean containsDuplicate(int[] nums) {Set<Integer> set = new HashSet<Integer>();for (int x : nums) {// if set don't contain x, return true if (!set.add(x)) {return true;}}return false;} }

復(fù)雜度分析

時(shí)間復(fù)雜度：O(N)，其中 N 為數(shù)組的長度。使用哈希集合（HashSet），添加元素的時(shí)間復(fù)雜度為 O(1)，遍歷數(shù)組時(shí)間復(fù)雜度為O（N）

空間復(fù)雜度：O(N)，其中 N 為數(shù)組的長度。算法創(chuàng)建了一個(gè)HashSet，占用空間趨向于O(N)，其他變量的空間復(fù)雜度均為常量

空間復(fù)雜度：算法的額外存儲(chǔ)空間

---

相似題

劍指 Offer 03. 數(shù)組中重復(fù)的數(shù)字
題目額外限定了數(shù)組元素的大小范圍，所以有時(shí)間復(fù)雜度 O(n)O(n)，空間復(fù)雜度 O(1)O(1) 的做法。

尋找重復(fù)數(shù)
題目也是額外限定了數(shù)組元素的大小范圍（注意限定條件和上題不同！），最優(yōu)做法是快慢指針。關(guān)于快慢指針的練習(xí)，還可以看這題快樂一下：202. 快樂數(shù)，我精心寫了題解。

刪除排序數(shù)組中的重復(fù)項(xiàng)
做法也是快慢指針。非常經(jīng)典的題目，C++ 標(biāo)準(zhǔn)庫的 unique 方法就是 這么實(shí)現(xiàn)的。非常值得一刷。

只出現(xiàn)一次的數(shù)字
超級經(jīng)典，我相信絕大多數(shù)人已經(jīng)做過了，沒有做過的速速去會(huì)會(huì)它。姊妹題：137. 只出現(xiàn)一次的數(shù)字 II 和 260. 只出現(xiàn)一次的數(shù)字 III。這兩題也是必刷題，刷了以后會(huì)對異或有更深入的了解和認(rèn)識。其中 劍指 Offer 56 - I. 數(shù)組中數(shù)字出現(xiàn)的次數(shù) 是重復(fù)題目，我提供了一種 使用二分解決的思路，值得一看哦～

TODO

2021.7.17

不理解力扣官方解法一的空間復(fù)雜度為什么是O($logN$)？

待整理相似題

整理最優(yōu)解

---

參考：

Java Arrays.sort()方法中使用的排序算法

Java Arrays.sort()方法的時(shí)間復(fù)雜度分析

官方解法

sweetiee的相似題整理

Python TimeComplexity

stackoverflow: What is time complexity of a list to set conversion?

總結(jié)

以上是生活随笔為你收集整理的存在重复元素的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。