Kth Largest Element in an Array; Sort; DAC; Heap;

We can use the idea of quichsort to solve this problem. First we set a pivot; which we let the first element of current array to be pivot; we set start to be the first element index and end to be the last element index of the array; we have two ways to find partition the current array;

One is we set left to be start and right to be end, and use a loop to scan the array. when left > right the loop ends. We at first scan the array from the left to find element smaller than the nums[pivot], and then scan the array from the right to left side to find element larget than nums[pivot], if(left<right) swap the two element. After the loop we swap the element of pivot and right. Then the right index is the exactly the index of the initial nums[pivot] and the left elements of the right position is larger than or equal to the nums[right] and all the right elements of the right position is smaller than or equal to the nums[right]. Now we compare k to right+1 if k == right+1 then we find the kth largest element ie nums[right] and if k > right +1 that means the target is in the right part of right position then we call the partition of the right part array with start = right+1 and end = end. Otherwise the target is in the left part of array. we call the partition method with start = start and end = right -1.

With this recursion we can find the kth largest element.

Another scan approach is just scan the array from the left to right. We initially set a variable pos to be start. If we find an element larger or equal to the pivot swap the current element with nums[pos]. and pos++. After the scan swap nums[pos] with nums[pivot]. 

Code:

public class Solution {
    // using quicksort algorithm
    public int findKthLargest(int[] nums, int k) {
        int len = nums.length;
        if(len == 0) return -1;
        if(len == 1) return nums[0];
        int start = 0, end = len-1;
        return partition(nums, 0, end, k);
    }
    
    public int partition(int[] nums, int start, int end, int k){
        int left = start, right = end;
        /*
        int pivot = end;
        int pos = start;
        for(int i = start; i < end; i++){
            if(nums[i] >= nums[pivot]) {
                swap(nums, i, pos);
                pos++;
            }
        }
        swap(nums, pivot, pos);
        if(k == pos+1) return nums[pos];
        else if(k < pos+1) return partition(nums, start, pos-1, k);
        else return partition(nums, pos+1, end, k);
        */
        
        int pivot = start;
        while(left <= right){
            while(left <= right && nums[left] >= nums[pivot]) left++;
            while(left <= right && nums[right] <= nums[pivot]) right--;
            if(left < right) swap(nums, left, right);
        }
        swap(nums, right, pivot);
        if(k == right+1) return nums[right];
        else if(k < right+1) return partition(nums, start, right-1, k);
        else return partition(nums, right+1, end, k);
    }
    
    public void swap(int[] nums, int left, int right){
        if(left == right) return;
        int temp = nums[left];
        nums[left] = nums[right];
        nums[right] = temp;
    }
}

Based on the above solution, there is an improvement. We can set use a method to sort the 3 element nums[start], nums[mid] and nums[end] from largest to smallest, here mid = (start+end)/2.　And then we swap start and mid elements, and set pivot = start.　

Kth Largest Element in an Array; Sort; DAC; Heap;

原文：http://www.cnblogs.com/5683yue/p/5229558.html