442. Find All Duplicates in an Array
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]
Success: 本來的做法update在github裡面，採用先sort在比對的方式，不過performance不好，所以跑去看論壇裡的解法
這題最快的人是用set寫，但是我覺得多開一個seen set這種做法應該不行，因為多用了extra space啊
自己實作論壇裡我認為可行的方法，發現一個有趣的現象，我理解後重寫成的版本(399 ms)，發現沒有原版本快，明明只差在< 和 >= ，不知道是不是跟access nums的行數有關係
class Solution(object):
def findDuplicates(self, nums):
"""
:type nums: List[int]
:rtype: List[int]
"""
result = [];
for x in nums:
if nums[abs(x)-1] < 0:
result.append(abs(x))
else:
nums[abs(x)-1] *= -1
return result
原版本(309 ms)
class Solution(object):
def findDuplicates(self, nums):
"""
:type nums: List[int]
:rtype: List[int]
"""
ret = []
for n in nums:
if nums[abs(n) - 1] >= 0:
nums[abs(n) - 1] *= -1
else:
ret.append(abs(n))
return ret
Fail:
1. Time Limit Exceeded ，list.count() complexity O( nlogn )
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]
Success: 本來的做法update在github裡面，採用先sort在比對的方式，不過performance不好，所以跑去看論壇裡的解法
這題最快的人是用set寫，但是我覺得多開一個seen set這種做法應該不行，因為多用了extra space啊
自己實作論壇裡我認為可行的方法，發現一個有趣的現象，我理解後重寫成的版本(399 ms)，發現沒有原版本快，明明只差在< 和 >= ，不知道是不是跟access nums的行數有關係
class Solution(object):
def findDuplicates(self, nums):
"""
:type nums: List[int]
:rtype: List[int]
"""
result = [];
for x in nums:
if nums[abs(x)-1] < 0:
result.append(abs(x))
else:
nums[abs(x)-1] *= -1
return result
原版本(309 ms)
class Solution(object):
def findDuplicates(self, nums):
"""
:type nums: List[int]
:rtype: List[int]
"""
ret = []
for n in nums:
if nums[abs(n) - 1] >= 0:
nums[abs(n) - 1] *= -1
else:
ret.append(abs(n))
return ret
Fail:
1. Time Limit Exceeded ，list.count() complexity O( nlogn )
