[LeetCode] 215. Kth Largest Element in an Array

Solution

Official solutions have several approaches including sorting, heap, and quick selecting. They are all great. I’d like to put forward another solution: Binary Search.

First, we can come to that the answer must be equal to or greater than the MIN element and equal to or smaller than the MAX element in the array. That is to say, the range of the answer is [min, max].

So, now let’s try to convert this problem into a decision one. By observing, we can find out that for a given x, if x is kth greatest element, there only k-1 elements are grater than x. For example, in array

[3,2,1,5,6,4] 

If I guess, 5 is 2nd greatest element, then I can only find one element 6 is greater than 5.

That is to say, for a given x, if there are k elements >= x, we should guess another bigger x.

Code

class Solution {
    int[] nums;
    int k;
    public int findKthLargest(int[] nums, int k) {
        this.nums = nums;
        this.k = k;
        int l = Integer.MAX_VALUE, r = Integer.MIN_VALUE;
        for (int x : nums) {
            l = Math.min(l, x);
            r = Math.max(r, x);
        }
        while (l + 1 < r ) {
            int mid = (l + r) / 2;
            if (check(mid)) {
                l = mid;
            } else {
                r = mid;
            }
        }
        if (check(r)) {
            return r;
        } 
        return l;
        
    }
    
    private boolean check(int x) {
        int count = 0;
        for (int e : nums) {
            if (e >= x) {
                count++;
            }
        }
        return count >= k;
    }
    
    
}

Time Complexity

O(nlog(max-min))

Similar Questions

https://leetcode.com/problems/k-closest-points-to-origin/

Author: huadonghu

Leave a Reply

Your email address will not be published. Required fields are marked *