作者:
Rushia (みけねこ的鼻屎)
2024-03-25 09:22:35https://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: