分治算法思想
在编程过程中，经常遇到处理数据相当多、求解过程比较复杂、直接求解会比较耗时的问题。在求解这类问题时，可以采用各个击破的方法。具体做法是：先把这个问题分解成几个较小的子问题，找到求出这几个子问题的解法后，再找到合适的方法，把它们组合成求整个大问题的解。如果这些子问题还是比较大，可以继续把它们分成几个更小的子问题，以此类推，直至可以直接求出解为止。
解题步骤
- 分解，将要解决的问题划分成若干个规模较小的同类问题。
- 求解，当子问题划分得足够小时，用较简单的方法解决。
- 合并，按原问题的要求，将子问题的解逐层合并构成原问题的解。
求顺序表中最大值
# 返回两个值中的最大值
def get_max(max_list):
if len(max_list) > 1 and max_list[0] <= max_list[1]:
return max_list[1]
else:
return max_list[0]
def solve(init_list):
n = len(init_list)
if n <= 2:
return get_max(init_list)
left_list, right_list = init_list[:n//2], init_list[n//2:]
left_max, right_max = solve(left_list), solve(right_list)
return get_max([left_max, right_max])
if __name__ == '__main__':
test_list = [12, 2, 23, 45, 67, 3, 2, 4, 45, 63, 24, 23]
print(solve(test_list)) # 67
判断某个元素是否在列表中
def is_in_list(init_list, el):
return [False, True][init_list[0] == el]
def solve(init_list, el):
n = len(init_list)
if n == 1:
return is_in_list(init_list, el)
left_list, right_list = init_list[:n//2], init_list[n//2:]
res = solve(left_list, el) or solve(right_list, el)
return res
if __name__ == '__main__':
test_list = [12, 2, 23, 45, 67, 3, 2, 4, 45, 63, 24, 23]
print(solve(test_list, 45)) # True
print(solve(test_list, 5)) # False
找出序列中第 k 小的元素
def partition(seq):
pi = seq[0]
lo = [x for x in seq[1:] if x <= pi]
hi = [x for x in seq[1:] if x > pi]
return lo, pi, hi
def select(seq, k):
lo, pi, hi = partition(seq)
m = len(lo)
if m == k - 1:
return pi
elif m < k - 1:
return select(hi, k - 1 - m)
else:
return select(lo, k)
if __name__ == '__main__':
test_list = [5, 2, 8, 7, 6, 3, 1, 4, 9, 10, 12, 11]
print(select(test_list, 7)) # 7
print(select(test_list, 3)) # 3
