-
Notifications
You must be signed in to change notification settings - Fork 0
/
p02_find_duplicate_numbers.py
69 lines (48 loc) · 1.69 KB
/
p02_find_duplicate_numbers.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
"""
p02_find_duplicate_numbers
~~~~~~~~~~~~~~
问题:找出数组中重复的数字
在一个长度为 n 的数组里,所有数字都在 0~n-1 范围内。数组中某些数字是重复的,但不知道
有几个数字重复了,也不知道每个数字重复了几次,要求找出任意一个重复的数字。
:copyright: (c) 2017 by 0xE8551CCB.
:license: MIT, see LICENSE for more details.
"""
from collections import deque
def merge_sort(seq):
if seq is None or len(seq) <= 1:
return seq
def merge(left_part, right_part):
merged, left_part, right_part = deque(), deque(left_part), deque(right_part)
while left_part and right_part:
merged.append(left_part.popleft() if left_part[0] < right_part[0] else right_part.popleft())
merged.extend(left_part if left_part else right_part)
return list(merged)
mid = len(seq) // 2
left = merge_sort(seq[:mid])
right = merge_sort(seq[mid:])
return merge(left, right)
def find_dup_numbers1(seq):
if seq is None or len(seq) <= 1:
return None
# 对数组排序再进行查找
seq = merge_sort(seq)
seen = []
for i in range(1, len(seq)):
if seq[i - 1] == seq[i]:
seen.append(seq[i])
return seen or None
def find_dup_numbers2(seq):
if seq is None or len(seq) <= 1:
return None
# 使用集合记录
seen = set()
dup = []
for x in seq:
if x not in seen:
seen.add(x)
else:
dup.append(x)
return dup or None
if __name__ == '__main__':
print(find_dup_numbers1([13, 3, 2, 1, 2, 8, 1]))
print(find_dup_numbers2([13, 3, 2, 1, 2, 8, 1]))