[LeetCode] 442. 數(shù)組中重復(fù)的數(shù)據(jù)

題目鏈接： https://leetcode-cn.com/problems/find-all-duplicates-in-an-array

難度：中等

通過(guò)率：61.5%

題目描述:

給定一個(gè)整數(shù)數(shù)組 a，其中1 ≤ a[i] ≤ n （ n 為數(shù)組長(zhǎng)度）, 其中有些元素出現(xiàn) 兩次 而其他元素出現(xiàn) 一次 。

找到所有出現(xiàn) 兩次 的元素。

你可以不用到任何額外空間并在O( n )時(shí)間復(fù)雜度內(nèi)解決這個(gè)問(wèn)題嗎？

示例:

**輸入:** [4,3,2,7,8,2,3,1]**輸出:** [2,3]

思路:

思路一：排序

通過(guò)索引號(hào)排序，比如數(shù)字4放到索引3的位置，最后找排序后數(shù)組，與索引號(hào)沒(méi)有相差1便是重復(fù)元素

思路二：絕對(duì)值

借用索引號(hào)，因?yàn)槭窃?~n之間，那么我們可以用索引0表示數(shù)字1，索引1表示數(shù)字2...，當(dāng)有個(gè)數(shù)字num，我們將num - 1的位置的數(shù)字取相反數(shù)，連續(xù)兩次取相反數(shù)會(huì)變回來(lái)，便可判斷元素出現(xiàn)次數(shù)。

所以時(shí)間復(fù)雜度為$O(n)$

相似題型：448. 找到所有數(shù)組中消失的數(shù)字

代碼：

思路一：

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]# 注意要保持這個(gè)位置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

總結(jié)

以上是生活随笔為你收集整理的angularjs 元素重复指定次数_[LeetCode] 442. 数组中重复的数据的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

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