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
76
77
78
|
chunkSize = 5
def findMedian(lst):
if len(lst) == 0:
return None
if len(lst) % 2 == 0:
num1 = findKth(lst, len(lst)//2)
num2 = findKth(lst, len(lst)//2 - 1)
num = (num1 + num2) * 1.0 / 2
else:
num = findKth(lst, len(lst)//2)
print("result: " + str(num))
return num
def findKth(lst, k):
if len(lst) == 0:
return None
if len(lst) == 1:
return lst[0]
medians = []
for i in range(0, len(lst), chunkSize):
chunk = lst[i:min(i + chunkSize, len(lst))]
chunk.sort()
median = chunk[len(chunk)//2]
medians.append(median)
medianOfMedians = findKth(medians, len(medians)//2)
# print("medianofmedians: " + str(medianOfMedians))
high = []
low = []
same = []
for num in lst:
if num < medianOfMedians:
low.append(num)
elif num > medianOfMedians:
high.append(num)
else:
same.append(num)
if len(low) > k:
return findKth(low, k)
elif len(low) + len(same) > k:
return medianOfMedians
else:
return findKth(high, k - len(low) - len(same))
assert findMedian([]) == None
assert findMedian([2]) == 2
assert findMedian([5,3]) == 4.0
assert findMedian([1,3]) == 2.0
assert findMedian([5,2,6]) == 5
assert findMedian([5,3,1]) == 3
assert findMedian([5,6,0,1]) == 3.0
assert findMedian([5,2,6,2,10,5]) == 5.0
assert findMedian([5,2,6,2,10,5,14]) == 5
assert findMedian([5,2,6,23,2,10,5,14]) == 5.5
assert findMedian([5,2,6,23,2,10,2, 5,14]) == 5
assert findMedian([5,2,6,23,2,10,2, 5,14, 5]) == 5.0
assert findMedian([5,2,6,23,2,10,2, 5,14, 12, 1349, 2, 349, 5, 10]) == 6
|
近期评论