[LeetCode] 442. Find All Duplicates in an Array

轉自LeetCode

Given an array of integers, 1 ≤ a[i] ≤ n (n = size of array), some elements appear twice and others appear once.

Find all the elements that appear twice in this array.

Could you do it without extra space and in O(n) runtime?

Example:

Input:
[4,3,2,7,8,2,3,1]

Output:
[2,3]

<Solution>

可以用 448. Find All Numbers Disappeared in an Array 一樣的思路

只是檢查條件不一樣

• 如果某個數 a 出現兩次，代表 nums[a-1] 在兩次取負值後，會變成正數

• 如果只出現一次，那麼值會是負值

• 如果沒出現，那麼根本不會被 access 到

code 如下

C++

Kotlin

這題也可以用 set 來解

如果 set 已經有值了，就代表重複了

時間複雜度一樣是 O(n)，但實際跑起來會比較慢

kotlin