滴滴第二题找第k大元素的O(n)复杂度解法
题目
在一个无序数组里找第K大的数
比如 array = [3, 4, 1, 2]，第一大的数是4，第四大的数是1。
解法1：排序
时间复杂度n*log(n)
解法2：partition
大家都记得快排里的partition函数吧？一次操作之后，可以知道轴元素在有序数组中的位置l，
- 如果l=k，那么轴元素就是所求；
- 如果l<k，说明k元素在l之后，缩小下标范围在后半段继续partition
- 如果l>k，说明k元素在l之前，在前半段继续partition。
注意：这里partition函数应当把大元素放在前面，小元素放在后面。
复杂度证明
第一次partition：n
第二次：n/2
第三次：n/4
第三次：n/8
n + n/2 + n/4 + n/8 + ... = 2n
上面是最优轴元素的情况，实际上不太可能恰好取到中位数，不过，复杂度仍然是O(n)。
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
List nums = new ArrayList();
String line = scanner.nextLine();
int k = scanner.nextInt();
scanner.close();
for (String num : line.split(" ")) {
nums.add(Integer.parseInt(num));
}
// time complexity is O(n)
int n = nums.size();
int[] array = new int[n];
for (int i = 0; i < n; i++) array[i] = nums.get(i);
int kth = findKth(array, n - k);
System.out.println(kth);
}
private static int findKth(int[] array, int k) {
int i = 0, j = array.length - 1;
int p;
while (true) {
p = partition(array, i, j);
if (p > k) j = p - 1;
else if (p < k) i = p + 1;
else break;
}
return array[p];
}
private static int partition(int[] array, int low, int high) {
int pivot = array[low];
int i = low;
int j = high + 1;
while (i < j) {
for (i++; i < high && array[i] < pivot; i++) ;
for (j--; j > low && array[j] > pivot; j--) ;
if (i < j) swap(array, i, j);
}
swap(array, low, j);
return j;
}
private static void swap(int[] array, int i, int j) {
int t = array[j];
array[j] = array[i];
array[i] = t;
}
}#滴滴#
投递美团等公司10个岗位 >
华为晋升空间 312人发布
