查找第 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
上一篇: 分治法的应用----求一个序列中第K大或第K小的数
下一篇: 查找_找出数组中最大的两个数