The problem

Find the kth largest element in an unsorted array. Note that it is the kth largest element inThe sorted order, not the KTH distinct element. Example 1: Input: [3,2,1,5,6,4] and k = 2 Output: 5 And k = 4 Output: 4 Note: You may assume k is always valid, 1 ≤ k ≤ array's length.
Copy the code

tag: Medium

Analysis of the

The easiest way to do this is to sort the array and return the KTH element directly. The complexity is O(NlogN). But, obviously, they didn’t want us to do that.

If you sort an array, it’s at least order NlogN. So if we don’t sort, can we figure out the KTH largest element? And the answer is yes, we know that one of the steps in quicksort is partition. It selects an element as the pivot, places all elements smaller than the pivot to the left, and all elements larger than the pivot to the right. It then returns the position of the hub in the array. Here, then, is the key. If the hub element is returned at exactly the desired location in the array, the problem is solved.

We start with a hub element, starting at the first element of the array and ending at the last. Swap the left element larger than the hub with the right element smaller than the hub. Then determine whether the index of the current hub element is N-k, if so, return the hub element directly. If index is greater than n-k, we continue recursively to the left of the hub, if index is less than n-k, we continue recursively to the right of the hub.

code

public class KthLargestElementInArray {

    public int findKthLargest(int[] nums, int k) {
        returnFindKth (nums, nums.length -k /*); findKth(nums, nums.length -k /*); } public int findKth(int[] nums, int k, int low, int high) {if (low >= high) {
            returnnums[low]; } int pivot = partition(nums, low, high); // Index of the hub elementif (pivot == k) {
            return nums[pivot];
        } else if(pivot < k) {// Pivot element index is less than k, continue to look for pivot elements on the rightreturn findKth(nums, k, pivot + 1, high);
        } else{// The index of the hub element is greater than kreturn findKth(nums, k, low, pivot - 1);
        }
    }

    int partition(int[] nums, int low, int high) {
        int i = low;
        int j = high + 1;
        int pivot = nums[low];
        while (true) {
            while (less(nums[++i], pivot)) {
                if (i == high) {
                    break; }}while (less(pivot, nums[--j])) {
                if (j == low) {
                    break; }}if (i >= j) {
                break;
            }
            swap(nums, i, j);
        }
        swap(nums, low, j);
        return j;
    }

    boolean less(int i, int j) {
        return i < j;
    }

    void swap(int[] nums, int i, int j) {
        if (i == j) {
            return; } int temp = nums[i]; nums[i] = nums[j]; nums[j] = temp; }}Copy the code

Complexity analysis

The complexity is O(N) + O(N / 2) + O(N / 4) +… The final algorithm complexity is O(N).