215. Kth Largest Element in an Array

Problem

Kth Largest Element in an Array

Approach

1. We could use MaxHeap to get current largest value from the array.
2. we could also use quick select to get the kth largest element.

Code

class Solution {
    private int Parent(int x){
        return (x - 1) / 2;
    }
    private int Left(int x){
        return 2 * x + 1;
    }
    private int Right(int x){
        return 2 * x + 2;
    }
    private void heapify(int pos, int n, int[] arr){
        int l = Left(pos);
        int r = Right(pos);
        int maxValueIndex = pos;
        if(l <= n && arr[l] > arr[maxValueIndex]){
            maxValueIndex = l;
        }
        if(r <= n && arr[r] > arr[maxValueIndex]){
            maxValueIndex = r;
        }
        if(maxValueIndex != pos){
            int temp = arr[pos];
            arr[pos] = arr[maxValueIndex];
            arr[maxValueIndex] = temp;
            heapify(maxValueIndex, n, arr);
        }
    }
    private void buildMaxHeap(int[] arr, int n){
        for(int i = Parent(arr.length - 1); i >= 0; i --){
            heapify(i, n, arr);
        }
    }
    public int findKthLargest(int[] nums, int k) {
        int n = nums.length - 1;
        buildMaxHeap(nums, n);
        for(int i = 0; i < k; i ++){
            int temp = nums[n];
            nums[n] = nums[0];
            nums[0] = temp;
            n --;
            heapify(0, n, nums);
        }
        return nums[n+1];
    }
}

// quick select, similar to quick sort
class Solution {
    private int quickSelect(int l, int r, int[] nums, int k){
        if(k > 0 && l <= r && k <= r - l + 1){
            int position = partition(l, r, nums);
            if(k == position - l + 1){
                return nums[position];
            }
            if(k < position - l + 1){
                return quickSelect(l, position - 1, nums, k);
            } else {
                return quickSelect(position + 1, r, nums, k - position + l -1);
            }
        }
        return -1;
    }
    private int partition(int l, int r, int[] nums){
        int pivot = nums[r], i = l;
        for(int j = l; j <= r - 1; j ++){
            if(nums[j] <= pivot){
                swap(i, j, nums);
                i ++;
            }
        }
        swap(i, r, nums);
        return i;
    }
    private void swap(int i, int j, int[] nums){
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
    public int findKthLargest(int[] nums, int k) {
        return quickSelect(0, nums.length - 1, nums, nums.length - k + 1);
    }
}