欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

查找第 K 大的数

程序员文章站 2022-05-12 10:57:44
...

题目

查找无序整数数组中第 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(n2)。

二分法

采用快排思想,取任意元素二分数组,假设当前位置为 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