[面试手撕]如何在不排序的情况下求数组的中位数：[数组]

给出一种非排序的方法，复杂度为O(NlogN)，但在实际执行时要比排序快(因为并不需要全排序)——

找到一组数据的中位数，就是找到第lenth/2的数，因此参考此题即可：

https://www.nowcoder.com/practice/673454422d1b4a168aed31e449d87c00

代码解释参考此篇：

https://blog.nowcoder.net/n/731472d8574c4b32817431a3ec8eb6c2

def find_k(arr, k):
    def split(low, high, k=0):
        if low >= high:
            return arr[low]
        i, j, p = low, high, low
        while i < j:
            while i < j and arr[j] >= arr[p]:  # 找到右边第一个小的
                j -= 1
            while i < j and arr[i] <= arr[p]:  # 找到左边第一个大的
                i += 1
            arr[i], arr[j] = arr[j], arr[i]
        arr[p], arr[j] = arr[j], arr[p]  # 把哨兵和最后一个找到的j对换

        offset = i - low  # 比 arr[i]小的有offset位
        if offset == k - 1:  # 左边有k位则当前即为第k小的
            return arr[i]
        elif offset > k - 1:
            return split(low, i - 1, k)
        else:
            return split(i + 1, high, k - offset - 1)
    return split(0, len(arr) - 1, k)


def find_mid(arr):
    l = len(arr)
    mid_a = find_k(arr, l // 2 + 1)
    return mid_a if l % 2 else (mid_a + find_k(arr, l // 2)) // 2

# ---IO---
n = int(input())
if n>0:
    arr = []
    for i in range(n):
        arr.append(int(input()))
    print(find_mid(arr))