There is an array of integers, please according to the idea of quick sorting, find the KTH largest number in the array. Given an array of integers, a, of size N and K(between 1 and n), return the KTH largest number to ensure the answer exists.

  • Example 1
Input [1,3,5,2,2],5,3 output 2Copy the code
Quicksort sorts an array into two parts, one smaller than a value and the other larger than that value. 1. Sort the array from largest to smallest in quicksort. Select a[start] as the first value of the array. 2. Assume that the key is the first number I array If I just equal to K, then the key is the first K value If I greater than K, it shows great value in the array on the left, the first K continues on the left to find if I less than K, it means that the K value on the right side of the array, continue to look for every round of sorting repeat the above steps in the right, until you find the K value.Copy the code

Quick row + dichotomy idea

import java.util.*; public class Solution { public int findKth(int[] a, int n, int K) { return quickSort(a,0,n-1,K); } public int quickSort(int[] a, int start,int end, int K){ int p=partition(a,start,end); if(p==K-1){ return a[K-1]; }else if(p>K-1){ quickSort(a,start,p-1,K); }else{ quickSort(a,p+1,end,K); } return a[K-1]; Public int partition(int[] arr,int start,int end){int key=arr[start]; while(start<end){ while(start<end&&arr[end]<=key){ end--; } swap(arr,start,end); while(start<end&&arr[start]>=key){ start++; } swap(arr,start,end); } return start; } public void swap(int[] arr,int left,int right){ int tem=arr[left]; arr[left]=arr[right]; arr[right]=tem; }}Copy the code