BiruLyu
7/24/2017 - 6:21 AM

## 215. Kth Largest Element in an Array(#Heap).java

``````public class Solution {
public int findKthLargest(int[] nums, int k) {
return quickSelect(nums, k - 1, 0, nums.length - 1);
}

private int quickSelect(int[] arr, int k, int left, int right){
int pivot = arr[(left + right) / 2];
int orgL = left, orgR = right;
while(left <= right){
// 从左向右找到第一个大于枢纽值的数
while(arr[left] > pivot){
left ++;
}
// 从右向左找到第一个小于枢纽值的数
while(arr[right] < pivot){
right --;
}
// 将两个数互换
if(left <= right){
swap(arr, left, right);
left ++;
right --;
}
}
// 最后退出的情况应该是右指针在左指针左边一格
// 这时如果右指针还大于等于k，说明kth在左半边
if(orgL < right && k <= right) return quickSelect(arr, k, orgL, right);
// 这时如果左指针还小于等于k，说明kth在右半边
if(left < orgR && k >= left) return quickSelect(arr, k, left, orgR);
return arr[k];

}

private void swap(int[] arr, int idx1, int idx2){
int tmp = arr[idx1] + arr[idx2];
arr[idx1] = tmp - arr[idx1];
arr[idx2] = tmp - arr[idx2];

}
}``````
``````public class Solution {
public int findKthLargest(int[] nums, int k) {
return quickSelect(nums, nums.length - k + 1, 0, nums.length - 1);
}

/*  quickselect is a selection algorithm to find the kth smallest element in an unordered list.
* low <= k <= high
* Returns the k-th smallest element of list within left..right inclusive
*/
private int quickSelect(int arr[],int k,int low,int high)
{

if(low == high) return arr[low];

// sort the mth largest element in the given array
int m = partition(arr,low,high);

// Adjust position relative to the current subarray being processed
int length = m - low + 1;

// If mth element is the median, return it
if(length == k)
{
return arr[m];
}

// If mth element is greater than median, search in the left subarray
if(length > k)
{
return quickSelect(arr,k,low,m-1);
}
// otherwise search in the right subArray
else
{
return quickSelect(arr,k-length,m+1,high);
}

}

private static int partition(int arr[],int low, int high)
{
// Get pivotvalue by finding median of medians
int pivotValue = getPivotValue(arr, low, high);

// Find the sorted position for pivotVale and return it's index
while(low < high)
{
while(arr[low] < pivotValue)
{
low ++;
}

while(arr[high] > pivotValue)
{
high--;
}

if(arr[low] == arr[high])
{
low ++;
}
if(low < high)
{
int temp = arr[low];
arr[low] = arr[high];
arr[high] = temp;
}

}
return high;
}

// Find pivot value, such the it is always 'closer' to the actual median
private static int getPivotValue(int arr[],int low,int high)
{
// If number of elements in the array are small, return the actual median
if(high-low+1 <= 5)
{
Arrays.sort(arr);
//return arr[arr.length/2];
return arr[low + (high - low + 1) / 2];
}

//Otherwise divide the array into subarray of 5 elements each, and recursively find the median

// Array to hold '5 element' subArray, last subArray may have less than 5 elements
int temp[] = null;

// Array to hold the medians of all '5-element SubArrays'
int medians[] = new int[(int)Math.ceil((double)(high-low+1)/5)];
int medianIndex = 0;

while(low <= high)
{
// get size of the next element, it can be less than 5
temp = new int[Math.min(5,high-low+1)];

// copy next 5 (or less) elements, in the subarray
for(int j=0;j<temp.length && low <= high;j++)
{
temp[j] = arr[low];
low++;
}

// sort subArray
Arrays.sort(temp);
// find mean and store it in median Array
medians[medianIndex] = temp[temp.length/2];
medianIndex++;
}

// Call recursively to find median of medians
return getPivotValue(medians,0,medians.length-1);
}

}``````
``````public class Solution {
public int findKthLargest(int[] nums, int k) {
return find(nums, k-1, 0, nums.length-1);
}

int find(int[] nums, int k, int left, int right) {
int orgL = left;
int orgR = right;
int pivot = (nums[left] + nums[right])/2;
while(left <= right) {
while(nums[left] > pivot)
left++;
while(nums[right] < pivot)
right--;
if (left<=right){
int tmp = nums[left];
nums[left] = nums[right];
nums[right] = tmp;
left++;
right--;
}
}
if (left<=k)  find(nums, k, left, orgR);
if (right >= k) find(nums,k, orgL, right);
return nums[k];
}
}``````
``````public class Solution {
public int findKthLargest(int[] nums, int k) {
PriorityQueue<Integer> minHeap = new PriorityQueue<>();
for (int num : nums) {
minHeap.offer(num);
if (minHeap.size() > k) {
minHeap.poll();
}
}
return minHeap.peek();
}
}``````