今天同样带来一道 leetcode 的算法题，主题同样是之前写的排序算法可不只是为了面试用的。
暴力
没啥好说的，暴力查找。我的这个写法有点类似于插入查找的思路，不同的是要从大到小进行排序，循环 k 次即可。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
|
public int findKthLargest(int[] nums, int k) {
int len = nums.length, maxIndex, temp;
for (int i = 0; i <= k; i++) {
maxIndex = i;
for (int j = i + 1; j < len; j++) {
if (nums[j] > nums[maxIndex]) {
maxIndex = j;
}
}
if (maxIndex > i) {
temp = nums[i];
nums[i] = nums[maxIndex];
nums[maxIndex] = temp;
}
}
return nums[k - 1];
}
|
平均时间复杂度为 O(k * n)，空间复杂度为 O(1)。
（我以为暴力法通不过，没想到竟然也过了）
排序
最朴素的方法，也是比较容易想到的，现成的库函数也有。（虽然也算一种方法，但直接调用库函数来排序肯定会被鄙视。。）
1
2
3
4
5
6
7
|
public int findKthLargest(int[] nums, int k) {
Arrays.sort(nums);
return nums[nums.length - k];
}
|
时间复杂度为 O(nlogn)，空间复杂度为 O(1)，原地排序。
堆
堆的性质及两个类型大家肯定还记得，解本题用一个小顶堆即可。
我们要保证堆中只有 k 个元素，当堆中元素超过 k 个时，就让最小元素（堆顶元素）出队。这样当所有元素经过这个操作后，堆中剩下的元素是待查找数组中的 k 个最大元素，而堆顶元素是这 k 个元素中的最小值，也就是答案。
java 中刚好也提供了现成的类可以用，那就是 PriorityQueue，而且它默认就是小顶堆，可真是省了不少事。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
|
public int findKthLargest(int[] nums, int k) {
PriorityQueue<Integer> heap = new PriorityQueue<>(k + 1);
for (int n: nums) {
heap.add(n);
if (heap.size() > k) {
heap.poll();
}
}
return heap.poll();
}
|
时间复杂度为 O(nlogk)，空间复杂度为 O(k)，用于存储堆元素。
利用快排思路
传送门：快速排序
之前的文章详细介绍过快排，那么我们知道两点：
- 数组中的第 k 个最大元素也就是第 n - k 个最小元素；
- 快排的 partition 操作，每次返回基准值在数组中排好序后的正确位置。
快排在每次 partition 结束后，还会再对基准值左右两边的子数组进行 partition 操作。而对于这道题，根据上边的第一点，我们可以在每次 partition 结束后，判断出正确结果在基准值左边还是右边，直接对某一边的子数组进行 partition 即可，直到找到正确结果。
这个算法和快排都是 Tony Hoare 发明的，因此也被称为 Hoare 选择算法。
之前详细介绍过快排，这里直接用三路快排来实现。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
|
public int findKthLargest(int[] nums, int k) {
return findKthLargestHelper(nums, 0, nums.length - 1, nums.length - k);
}
private int findKthLargestHelper(int[] nums, int left, int right, int k) {
int randomIndex = (int) (Math.random() * (right - left + 1)) + left;
int temp = nums[left];
nums[left] = nums[randomIndex];
nums[randomIndex] = temp;
int pivot = nums[left], lt = left, gt = right + 1, i = left + 1;
while (i < gt) {
if (nums[i] < pivot) {
temp = nums[i];
nums[i] = nums[lt + 1];
nums[lt + 1] = temp;
i ++;
lt ++;
} else if (nums[i] > pivot) {
temp = nums[i];
nums[i] = nums[gt - 1];
nums[gt - 1] = temp;
gt --;
} else {
i ++;
}
}
nums[left] = nums[lt];
nums[lt] = pivot;
if (k < lt) {
return findKthLargestHelper(nums, left, lt - 1, k);
} else if (k > gt - 1) {
return findKthLargestHelper(nums, gt, right, k);
} else {
return pivot;
}
}
|
平均时间复杂度为 O(n)，空间复杂度为 O(1)，原地查找。不得不说，这个时间复杂度还是比较令人满意的。