1 # -*- coding: utf-8 -*-
2 import math
3
4 def merge(l1, l2):
5 list_merge = []
6 i = j = 0
7 while i < len(l1) and j < len(l2):
8 if l1[i] < l2[j]:
9 list_merge.append(l1[i])
10 i += 1
11 else:
12 list_merge.append(l2[j])
13 j += 1
14 if i == len(l1):
15 while j < len(l2):
16 list_merge.append(l2[j])
17 j += 1
18 else:
19 while i < len(l1):
20 list_merge.append(l1[i])
21 i += 1
22 return list_merge
23
24 def problem_9_3_8(list1, list2, l1, r1, l2, r2):
25 if l1 == r1:
26 if list1[l1] < list2[l2]:
27 return list1[l1], list2[l2]
28 else:
29 return list2[l2], list1[l1]
30
31 if (r1 - l1 + 1) % 2: # 每个数组中元素是奇数，分别只有一个中位数
32 l1_m = (r1 + l1) // 2
33 l2_m = (r2 + l2) // 2
34 if list1[l1_m] < list2[l2_m]:
35 return problem_9_3_8(list1, list2, l1_m, r1, l2, l2_m)
36 elif list1[l1_m] > list2[l2_m]:
37 return problem_9_3_8(list1, list2, l1, l1_m, l2_m, r2)
38 else:
39 return list1[l1_m], list2[l2_m]
40 else : # 每个数组中元素是偶数，则分别有两个中位数 此时有C(3,1)+C(3,2) = 6种情况
41 l1_m1 = math.floor((r1 + l1) / 2)
42 l1_m2 = math.ceil((r1 + l1) / 2)
43
44 l2_m1 = math.floor((r2 + l2) / 2)
45 l2_m2 = math.ceil((r2 + l2) / 2)
46
47 if (list1[l1_m2] <= list2[l2_m1]) : # L1下 <= L1上 <= L2下 <= L2上
48 return problem_9_3_8(list1, list2, l1_m2, r1, l2, l2_m1)
49 elif list2[l2_m2] <= list1[l1_m1]: # L2下 <= L2上 <= L1下 <= L1上
50 return problem_9_3_8(list1, list2, l1, l1_m1, l2_m2, r2)
51 elif (list1[l1_m1] <= list2[l2_m1]) and (list2[l2_m1] <= list1[l1_m2]) and (list1[l1_m2] <= list2[l2_m2]): # L1下 <= L2下 <= L1上 <= L2上
52 return list2[l2_m1], list1[l1_m2]
53 elif (list2[l2_m1] <= list1[l1_m1]) and (list1[l1_m1] <= list2[l2_m2]) and (list2[l2_m2] <= list1[l1_m2]): # L2下 <= L1下 <= L2上 <= L1上
54 return list1[l1_m1], list2[l2_m2]
55 elif (list2[l2_m1] <= list1[l1_m1]) and (list1[l1_m2] <= list2[l2_m2]): # L2下 <= L1下 <= L1上 <= L2上
56 return list1[l1_m1], list1[l1_m2]
57 else: # (list1[l1_m1] <= list2[l2_m1]) and (list2[l2_m2] <= list1[l1_m2]): # L1下 <= L2下 <= L2上 <= L1上
58 return list2[l2_m1], list2[l2_m2]
59
60
61 list1 = [i*11 for i in range(300)]
62 list2 = [i*7 for i in range(300)]
63
64 list4 = merge(list1, list2)
65 print(list4)
66 print(list4[math.floor((len(list4)-1)/2)], list4[math.ceil((len(list4)-1)/2)])
67
68 m1,m2 = problem_9_3_8(list1, list2, 0, len(list1)-1, 0, len(list2)-1)
69 print(m1,m2)
