-
Notifications
You must be signed in to change notification settings - Fork 19
/
04_Find-Duplicates.py
55 lines (44 loc) · 1.36 KB
/
04_Find-Duplicates.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
#!/usr/bin/python
# coding=utf-8
'''
__author__ = 'sunp'
__date__ = '2019/1/24'
Given an array of integers where each value 1 <= x <= len(array), write a function that finds all the duplicates in the array.
dups([1, 2, 3]) = []
dups([1, 2, 2]) = [2]
dups([3, 3, 3]) = [3]
dups([2, 1, 2, 1]) = [1, 2]
Notes: result no need in same order, revert the original array if in-place modification not allowed.
'''
from collections import Counter
def dups1(nums):
# hashmap: O(n) time, O(n) space
d = {}
for num in nums:
d[num] = d.get(num, 0) + 1
return [k for k, v in d.items() if v > 1]
def dups2(nums):
# counting array: O(n) time, O(n) space
count = [0 for _ in range(len(nums)+1)]
res = []
for num in nums:
if count[num] == 1:
res.append(num)
count[num] += 1
return res
def dups3(nums):
# mapping base on '1 <= x <= len(nums)': O(n) time, O(1) space
res = set()
for i in range(len(nums)):
sign = abs(nums[i]) - 1
if nums[sign] > 0:
nums[sign] = -nums[sign]
else:
res.add(abs(nums[i]))
return list(res)
if __name__ == '__main__':
for dups in [dups1, dups2, dups3]:
assert dups([1, 2, 3]) == []
assert dups([1, 2, 2]) == [2]
assert dups([3, 3, 3]) == [3]
assert Counter(dups([2, 1, 2, 1])) == Counter([1, 2])