剑指 Offer II 076. 数组中的第 k 大的数字

剑指 Offer II 076. 数组中的第 k 大的数字

很容易想到堆，但感觉不算最好的办法，先写个堆的代码。

class Solution {
    public int findKthLargest(int[] nums, int k) {
        PriorityQueue<Integer> minHeap = new PriorityQueue<>();
        for(int i=0; i<nums.length; i++) {
            if(minHeap.size() < k) {
                minHeap.add(nums[i]);
            } else {
                if(minHeap.peek() < nums[i]) {
                    minHeap.add(nums[i]);
                    minHeap.poll();
                }
            }
        }
        return minHeap.peek();

    }
}

通过快速排序得到的

  public int findKthLargest(int[] nums, int k) {
        int left = 0;
        int right = nums.length - 1;
        k = nums.length - k;
        while (left <= right) {
            int i = merge(nums, left, right);
            if(i == k) {
                return nums[i];
            }
            if(i < k) {
                left = i + 1;
            } else {
                right = i - 1;
            }
        }
        return -1;
    }

    public static int merge(int[] nums, int left, int right) {
        int flag = nums[left];
        while (left < right) {
            while (left < right && nums[right] > flag) {
                right--;
            }
            swap(nums, left, right);
            while (left < right && nums[left] <= flag) {
                left++;
            }
            swap(nums, left, right);
        }
        return left;
    }
    public static void swap(int[] nums, int left, int right) {
        int temp = nums[left];
        nums[left] = nums[right];
        nums[right] = temp;
    }