查找第 K 大的数

题目

查找无序整数数组中第 K 大的元素。

示例

输入：[1, 0, 5, -1, 3, 2, 4], 3

输出：1

解答

冒泡法

采用冒泡排序思想，执行 K 次冒泡，即可得到结果。

public int find(int[] data, int k) {
    for (int i = 0; i < k; i++) {
        for (int j = 0; j < data.length - i - 1; j++) {
            if (data[j + 1] < data[j]) ArrayUtils.swap(data, j + 1, j);
        }
    }
    return data[data.length - k];
}

时间复杂度依赖 K 值大小，最好为 o(n)，最坏为 o(n²)。

二分法

采用快排思想，取任意元素二分数组，假设当前位置为 p，则 p 左边的元素全小于 p 元素，右边则全大于。p + 1 则代表该元素在数组中大小的位置。

public int find(int[] data, int p, int q, int k) {
    int left = p, right = q;
    while (p < q) {
        int key = data[p];
        while (p < q && data[q] <= key) q--;
        ArrayUtils.swap(data, left, q);
        while (p < q && data[p] <= key) p++;
        ArrayUtils.swap(data, left, p);
    }
    if (k == p + 1) {
        return data[p];
    } else if (k > p + 1) {
        return find(data, p + 1, right, k);
    } else {
        return find(data, left, p, k);
    }
}

由最外层 n 次遍历，一分为二依次遍历，时间复杂度为 o(n)。

效率

模拟 100w 个无序元素数组，查找第 1k 大的元素；

public static void main(String[] args) {
    long s;

    ArrayFind find = new ArrayFind();
    int k = 1_000;
    int n = 100_0000;
    int[] a = ArrayUtils.initArray(n);

    s = System.currentTimeMillis();
    find.find(a, 0, a.length - 1, k);
    System.out.println("binary cost " + (System.currentTimeMillis() - s));

    int[] b = ArrayUtils.initArray(n);
    s = System.currentTimeMillis();
    find.find(b, k);
    System.out.println("bubble cost " + (System.currentTimeMillis() - s));
}

输出：

binary cost 289
bubble cost 1911