Re: [閒聊] 每日leetcode
https://leetcode.com/problems/find-all-duplicates-in-an-array
442. Find All Duplicates in an Array
給你一個大小為 n 的陣列，裡面只包含1~n，每個元素只會出現一次或兩次，求出哪些
數字出現超過一次。
你必須使用常數空間和線性時間複雜度。
思路：
1.把整個陣列當成一個 map，因為數字只在1~n的關係不需額外空間，每次都把
nums[i] - 1 位置的索引標記成負數(乘上-1)，如果某次走訪時發現已經是負的
就表示當前值重複出現了。
pycode:
--------------------------------------------------------------------
class Solution:
def findDuplicates(self, nums: List[int]) -> List[int]:
res = []
for i in range(len(nums)):
idx = abs(nums[i]) - 1
if nums[idx] < 0:
res.append(abs(nums[i]))
else:
nums[idx] *= -1
return res
--------------------------------------------------------------------
--
https://i.imgur.com/AhrL1pB.jpg
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 101.138.175.27 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1711329758.A.F2B.html
推
03/25 09:23,
1年前
, 1F
03/25 09:23, 1F
推
03/25 09:24,
1年前
, 2F
03/25 09:24, 2F
推
03/25 09:24,
1年前
, 3F
03/25 09:24, 3F
→
03/25 09:25,
1年前
, 4F
03/25 09:25, 4F
→
03/25 09:25,
1年前
, 5F
03/25 09:25, 5F
→
03/25 09:26,
1年前
, 6F
03/25 09:26, 6F
推
03/25 09:26,
1年前
, 7F
03/25 09:26, 7F
討論串 (同標題文章)
完整討論串 (本文為第 69 之 1548 篇)：