[LeetCode] 442. 數組中重復的數據
題目鏈接： https://leetcode-cn.com/problems/find-all-duplicates-in-an-array
難度：中等
通過率：61.5%
題目描述:
給定一個整數數組 a，其中1 ≤ a[i] ≤ n （ n 為數組長度）, 其中有些元素出現 兩次 而其他元素出現 一次 。
找到所有出現 兩次 的元素。
你可以不用到任何額外空間并在O( n )時間復雜度內解決這個問題嗎？
示例:
**輸入:**
[4,3,2,7,8,2,3,1]**輸出:**
[2,3]思路:
思路一：排序
通過索引號排序，比如數字4放到索引3的位置，最后找排序后數組，與索引號沒有相差1便是重復元素
思路二：絕對值
借用索引號，因為是在1~n之間，那么我們可以用索引0表示數字1，索引1表示數字2...，當有個數字num，我們將num - 1的位置的數字取相反數，連續兩次取相反數會變回來，便可判斷元素出現次數。
所以時間復雜度為$O(n)$
相似題型：448. 找到所有數組中消失的數字
代碼：
思路一：
class Solution:def findDuplicates(self, nums: List[int]) -> List[int]:res = []for i in range(len(nums)):while nums[nums[i] - 1] != nums[i]:tmp = nums[i]# 注意要保持這個位置loc = nums[i] - 1nums[i] = nums[nums[i] - 1]nums[loc] = tmpfor idx, val in enumerate(nums, 1):if val != idx:res.append(val)return res思路二：
class Solution:def findDuplicates(self, nums: List[int]) -> List[int]:res = []for i in range(len(nums)):loc = abs(nums[i]) - 1if nums[loc] < 0:res.append(loc + 1)nums[loc] = -nums[loc]return res
