LeetCode: 215. Kth Largest Element in an Array 数组中第k大元素

梦里梦外; 2021-06-24 16:10 481阅读 0赞

试题:
Find the kth largest element in an unsorted array. Note that it is the kth largest element in the sorted order, not the kth distinct element.

Example 1:

Input: [3,2,1,5,6,4] and k = 2
Output: 5
Example 2:

Input: [3,2,3,1,2,4,5,5,6] and k = 4
Output: 4
Note:
You may assume k is always valid, 1 ≤ k ≤ array’s length.
代码:
topk或者kth element问题通常可以使用快排和堆排解决。快排找出kth后再遍历一遍就能找到topk;堆排的堆顶就是kth element。

  1. class Solution {
  2. public int findKthLargest(int[] nums, int k) {
  3. Arrays.sort(nums);
  4. return nums[nums.length-k];
  5. }
  6. }
  7. class Solution {
  8. public int findKthLargest(int[] nums, int k) {
  9. PriorityQueue<Integer> que = new PriorityQueue<Integer>(k);
  10. for(int num : nums){
  11. if(que.size()<k)
  12. que.offer(num);
  13. else if(que.peek()<num){
  14. que.offer(num);
  15. que.poll();
  16. }
  17. }
  18. return que.peek();
  19. }
  20. }
  21. //快速选择法
  22. class Solution {
  23. public int findKthLargest(int[] nums, int k) {
  24. k = nums.length-k;
  25. int low=0, high=nums.length-1;
  26. while(low<high){ //不需要等于,当low=high-1时,已经排序好数组了。
  27. int part = partition(nums, low, high);
  28. if(part==k){
  29. break;
  30. }else if(part<k){
  31. low = part+1;
  32. }else{
  33. high = part-1;
  34. }
  35. }
  36. return nums[k];
  37. }
  38. private int partition(int[] nums, int low, int high){
  39. int left=low, right=high+1;
  40. while(true){
  41. while(nums[++left]<nums[low] && left<high);
  42. while(nums[--right]>nums[low] && right>low);
  43. if(left>=right) break;
  44. swap(nums,left,right);
  45. }
  46. swap(nums,low,right);
  47. return right;
  48. }
  49. private void swap(int[] nums, int left, int right){
  50. int tmp = nums[left];
  51. nums[left] = nums[right];
  52. nums[right] = tmp;
  53. }
  54. }
  55. class Solution {
  56. public int findKthLargest(int[] nums, int k) {
  57. int len = nums.length;
  58. k = len - k;
  59. quickSort(nums, 0, len-1, k);
  60. return nums[k];
  61. }
  62. public void quickSort(int[] nums, int start, int end, int target){
  63. if(start < end){
  64. int mid = partion(nums, start, end);
  65. if(mid == target){
  66. return;
  67. }else if(mid > target){
  68. quickSort(nums, start, mid-1, target);
  69. }else if(mid < target){
  70. quickSort(nums, mid+1, end, target);
  71. }
  72. }
  73. }
  74. public int partion(int[] nums, int start, int end){
  75. int pivot = nums[start];
  76. int left = start, right = end;
  77. while(left < right){
  78. while(left < right && nums[right] >= pivot) right--;
  79. while(left < right && nums[left] <= pivot) left++;
  80. if(left < right){
  81. swap(nums, left, right);
  82. }
  83. }
  84. swap(nums, start, right);
  85. return right;
  86. }
  87. public void swap(int[] nums, int i, int j){
  88. int temp = nums[i];
  89. nums[i] = nums[j];
  90. nums[j] = temp;
  91. return;
  92. }
  93. }

发表评论

表情:
评论列表 (有 0 条评论,481人围观)

还没有评论,来说两句吧...

相关阅读