Leetcode 215. Kth Largest Element in an Array

Approach 1: sort

• sort the array using merge sort (n log n)
• return the kth largest element in the sorted array

class Solution {
    public int findKthLargest(int[] nums, int k) {
        if (nums.length < k) {
            return -1;
        }
        Arrays.sort(nums);
        return nums[nums.length - k];
    }
}

Approach 2: heap

• Create a min-heap and always keep the size less or equal to k
• push all elements of the array into the min-heap: when the heap size less than k, push elements, else, replace the root element of the heap only if the element is greater than the root.
• so that what's left in the min-heap is the largest k element of the array, and since it's a min-heap, the root element is the kth largest element of the array.
• O(n lg k)
• 注意事项：用array来表示heap是，要从index为1开始，这样left才会等于，

class Solution {
    public int findKthLargest(int[] nums, int k) {
        if (nums.length < k) {
            return -1;
        }
        // index 0 not used
        int[] minHeap = new int[k+1];
        int size = 0;
        for(int val: nums) {
            if (size < k) {
                insert(minHeap, size, val);
                size++;
            } else if(val > minHeap[1]) {
                replaceRoot(minHeap, val, size);
            }
        }
        return minHeap[1];
        
    }
    public void insert(int[] minHeap, int size, int val) {
        minHeap[size+1] = val;
        int i = size+1;
        while(i > 1) {
            int parent = i/2;
            if (minHeap[i] < minHeap[parent]) {
                int tmp = minHeap[i];
                minHeap[i] = minHeap[parent];
                minHeap[parent] = tmp;
                i = parent;
            } else {
                break;
            }
        }
    }
    public void replaceRoot(int[] minHeap, int val, int size) {
        minHeap[1] = val;
        int i = 1;
        while(i <= size/2) {
            int mini = i;
            if (i*2 <= size && minHeap[mini] > minHeap[i*2]) {
                mini = i*2;
            }
            if (i*2+1 <= size && minHeap[mini] > minHeap[i*2+1]) {
                mini = i*2+1;
            }
            if (mini == i) {
                break;
            } else {
                int tmp = minHeap[i];
                minHeap[i] = minHeap[mini];
                minHeap[mini] = tmp;
                i = mini;
            }
        }
    }
}

Approach 3: QuidkSort

• choose random number as pivot
• move numbers smaller than pivot to the left: partition algorithm
• choose left or right part to proceed

class Solution {
    public int findKthLargest(int[] nums, int k) {
        if (nums.length < k) {
            return -1;
        }
        return helper(nums, 0, nums.length-1, k);
    }
    public int helper(int[] nums, int start, int end, int k) {
        // choose the random number between start and end as the index of pivot
        int pivotIdx = start + (int) Math.random() * ((end - start) + 1);
        int pivotPos = partition(nums, start, end, pivotIdx);
        if (end - pivotPos + 1 == k) {
            return nums[pivotPos];
        } else if (end - pivotPos + 1 < k) {
            return helper(nums, start, pivotPos-1, k-(end - pivotPos + 1));
        }
        return helper(nums, pivotPos + 1, end, k);
        
    }
    public int partition(int[] nums, int start, int end, int idx) {
        int pivot = nums[idx];
        // move pivot to the end
        swap(nums, idx, end);
        
        // move elements smaller than pivot to the left side
        // pointer to record the last element that smaller than pivot
        // so the array been split to 3 part: smaller than pivot, greater, pivot
        int p = start;
        for (int i = start; i < end; i++) {
            if (nums[i] < pivot) {
                swap(nums, i, p);
                p++;
            }
        }
        
        /// put the pivot to the middle of smaller and greater part
        swap(nums, p, end);
        return p;
    }
    public void swap(int[] nums, int i, int j) {
        int tmp = nums[i];
        nums[i] = nums[j];
        nums[j] = tmp;
    }
}