一定要早日上岸鸭 · July 17, 2021 0

215. 数组中的第K个最大元素

215. 数组中的第K个最大元素

给定整数数组 nums 和整数 k，请返回数组中第 k 个最大的元素。

请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。

class Solution { public void swap(int[]q, int l, int r){ int temp = q[l]; q[l] = q[r]; q[r] = temp; } public int quickSelect(int[]q, int l, int r, int k){ // 基于快排的快选 // 快排模板： if(l>=r) return q[k]; int i = l-1, j=r+1, x = q[l+r>>1]; System.out.println(x); while(i<j){ do{i++;} while(q[i]>x); do{j--;} while(q[j]<x); if(i<j) swap(q, i, j); System.out.println(Arrays.toString(q)); } System.out.println("final: "+Arrays.toString(q)+" "+j); if(j>=k) return quickSelect(q, l, j, k); else { System.out.println(Arrays.toString(q)+" "+r); return quickSelect(q, j+1, r, k); } } public void quickSort(int[]q, int l, int r){ // 快排（降序） if(l>=r) return; int i = l-1, j=r+1, x = q[l+r>>1]; while(i<j){ do{i++;} while(q[i]>x); do{j--;} while(q[j]<x); if(i<j) swap(q, i, j); } quickSort(q, l, j); quickSort(q, j+1, r); } public int findKthLargest(int[] nums, int k) { quickSort(nums, 0, nums.length-1); System.out.println(Arrays.toString(nums)); // return quickSelect(nums, 0, nums.length-1, k-1); // System.out.println(Arrays.toString(nums)); return nums[k-1]; } }

Tags:

You may also like...

Leave a Reply

Your email address will not be published. Required fields are marked *