今天同样带来一道 leetcode 的算法题,主题同样是之前写的排序算法可不只是为了面试用的。
![](/images/12-1.png)
暴力
没啥好说的,暴力查找。我的这个写法有点类似于插入查找的思路,不同的是要从大到小进行排序,循环 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)。
(我以为暴力法通不过,没想到竟然也过了)
![](/images/12-2.png)
排序
最朴素的方法,也是比较容易想到的,现成的库函数也有。(虽然也算一种方法,但直接调用库函数来排序肯定会被鄙视。。)
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),原地查找。不得不说,这个时间复杂度还是比较令人满意的。