算法经典问题之第k大/小问题(寻找中位数)

• 算法经典问题之第k大/小问题(寻找中位数)
• 问题描述
• 解法
• python实现

问题描述

从n个未排序的数中找出第k小的数。
有直接解法是先排序再拿第k个数即可，但是最好的算法也要(O(n\lg{n}))。
下面的解法更优。

解法

这个其实是利用的分治法思考，和二分查找很像。
和快速排序同样的过程，先随机选一个数，然后把比它小的放到左边，比它大的放到右边。设排完后这个数的索引是m,
对比m和k,
如果m==k,说明这个数就是我们要找的。
如果m<k, 说明前m个数都比要找的数小。从而问题变为从右边的数中找到第k-m小的数。
如果m>k,说明要找的数在前m个数中，从而问题变为从右边的数中找到第k小的数。

按此算法，它的时间效率是O(n)。

python实现

#!/usr/bin/env python
import random


def min_k(data, k):

    def swap(i, j):
        temp = data[i]
        data[i] = data[j]
        data[j] = temp

    n = len(data)
    s = random.randint(0, n-1)
    swap(s, 0)
    j = 1
    key = data[0]
    for i in range(1, n):
        if data[i] < key:
            swap(j, i)
            j += 1
    swap(j-1, 0)
    if j == k:
        return data[j-1]
    elif j > k:
        return min_k(data[0:j-1], k)
    else:
        return min_k(data[j:], k-j)