题目
有一个无序的整数序列(无重复项,长度为奇数),请用你认为最优的方法求序列的中位数.
例如给定数组1, 5, 2, 9, 8, 0, 6,中位数是5.
要求算法的时间复杂度需要小于O(n**2),不能使用内置排序函数,可以使用任何语言实现.
def find_mid(li):
quick_sort(li, 0, len(li) - 1)
tar = len(li) // 2
return len(li), tar, li[tar]
def quick_sort(li, first, last):
if first > last:
return
# 找到基准值的正确位置下表索引
split_pos = part(li, first, last)
# 递归思想,因为基准值正确位置左侧继续快排,基准值正确位置的右侧继续快排
quick_sort(li, first, split_pos - 1)
quick_sort(li, split_pos + 1, last)
def part(li, first, last):
"""找到基准值的正确位置,返回下标索引"""
# 基准值、左游标、右游标
mid = li[first]
lcursor = first + 1
rcursor = last
sign = False
while not sign:
# 左游标右移 - 遇到比基准值大的停
while lcursor <= rcursor and li[lcursor] <= mid:
lcursor += 1
# 右游标左移 - 遇到比基准值小的停
while lcursor <= rcursor and li[rcursor] >= mid:
rcursor -= 1
# 当左游标 > 右游标时,我们已经找到了基准值的正确位置,不能再移动了
if lcursor > rcursor:
sign = True
# 基准值和右游标交换值
li[first], li[rcursor] = li[rcursor], li[first]
else:
# 左右游标互相交换值
li[lcursor], li[rcursor] = li[rcursor], li[lcursor]
return rcursor
if __name__ == '__main__':
li = [5, 2, 9, 8, 0, 6, 11, 7, 15, 3, 16]
result = find_mid(li)
print(li)
print(result)
# 输出结果
# [0, 2, 3, 5, 6, 7, 8, 9, 11, 15, 16] 排序结果li
# (11, 5, 7) li的长度,tar,中位数