-
Notifications
You must be signed in to change notification settings - Fork 80
/
FindDuplicates.py
75 lines (54 loc) · 2.14 KB
/
FindDuplicates.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
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
"""
Title: Find Duplicates
Given an array of integers where each value 1 <= x <= len(array), write a
function that finds all the duplicates in the array.
Execution: python FindDuplicates.py
For more details, check out http://www.byte-by-byte.com/findduplicates/
"""
import unittest
def find_duplicates(arr):
"""
Return a list of duplicates in the array. To avoid using extra space,
we flag which elements we've seen before by negating the value at
indexed at that value in the array.
"""
# Use a set for results to avoid duplicates.
result_set = set()
for i in range(len(arr)):
# Translate the value into an index (1 <= x <= len(arr))
idx = abs(arr[i]) - 1
# If the value at that index is negative, then we've already seen
# that value so it's a duplicate. Otherwise, negate the value at
# that index we know we've seen it.
if arr[idx] < 0:
result_set.add(abs(arr[i]))
else:
arr[idx] = -arr[idx]
# Return the list to it's original state.
for i in range(len(arr)):
arr[i] = abs(arr[i])
return list(result_set)
class TestFindDuplicates(unittest.TestCase):
def test_len_1_no_dups(self):
self.assertEqual(find_duplicates([1]), [])
print("Length 1, no duplicates")
def test_len_2_no_dups(self):
self.assertEqual(find_duplicates([1, 2]), [])
print("Length 2, no duplicates")
def test_len_2_dups(self):
self.assertEqual(find_duplicates([1, 1]), [1])
print("Length 2, duplicates")
def test_len_4_no_dups(self):
self.assertEqual(find_duplicates([1, 2, 3, 4]), [])
print("Length 4, no duplicates")
def test_len_4_one_dup(self):
self.assertEqual(find_duplicates([1, 1, 2, 3]), [1])
print("Length 4, one duplicate")
def test_len_4_two_dups(self):
self.assertEqual(find_duplicates([1, 1, 2, 2]), [1, 2])
print("Length 4, two duplicates")
def test_len_4_repeat_dups(self):
self.assertEqual(find_duplicates([1, 1, 1, 1]), [1])
print("Length 4, repeated 4 times.")
if __name__ == '__main__':
unittest.main()