simple JAVA solution O(n) with just the same idea of quick sort


  • 0
    public class Solution {
        public int findKthLargest(int[] nums, int k) {
            if (nums.length == 0) {return Integer.MAX_VALUE;}
            if (nums.length == 1) {return nums[0];}
            return findKth(nums, nums.length - k, 0, nums.length - 1);
        }
        
        public int findKth(int[] nums, int pos, int low, int high) {
            // simliar with the quick sort program. Now return if the nums[pos] is the kth largest
            // System.out.println(Arrays.toString(nums) + "  " +Integer.toString(low) + "   "+Integer.toString(high));
            int start = low;
            int end = high;
            int pivot = nums[pos];
            while (start <= end) {
                while (nums[start] < pivot) {
                    start ++;
                } 
                while (nums[end] > pivot) {
                    end --;
                }
                if (start == pos && end == pos) {
                    return nums[pos];
                } 
                if (start <= end) {
                    int tmp = nums[start];
                    nums[start] = nums[end];
                    nums[end] = tmp;
                    start ++;
                    end --;
                }
            }
            if (start <= pos) {
                return findKth(nums, pos, start, high);
            } 
            return findKth(nums, pos, low, end);
        }
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.