思路

堆

思路是创建一个大顶堆，将所有数组中的元素加入堆中，并保持堆的大小小于等于 k。这样，堆中就保留了前 k 个最大的元素。这样，堆顶的元素就是正确答案。

像大小为 k 的堆中添加元素的时间复杂度为O(logk)，我们将重复该操作 N 次，故总时间复杂度O(Nlogk)。

public int findKthLargest(int[] nums, int k) {
        PriorityQueue<Integer> heap = new PriorityQueue<>((n1,n2)->n1-n2);
        for(int n:nums){
            heap.add(n);
            if(heap.size()>k)
                heap.poll();
        }
        return heap.peek();
    }

快速排序

使用快速排序的思想

  public int findKthLargest(int[] nums, int k) {
        return quickSelect(nums,0,nums.length-1,k);
    }
    int quickSelect(int[] nums,int low,int high,int k){
        int pivot = low;
        for (int j = low; j < high; j++) {
            if (nums[j] <= nums[high]) {
              swap(nums, pivot++, j);
            }
        }
        swap(nums, pivot, high);
        int count = high - pivot + 1;
        // pivot is the one!
        if (count == k) return nums[pivot];
        // pivot is too small, so it must be on the right
        if (count > k) return quickSelect(nums, pivot + 1, high, k);
        // pivot is too big, so it must be on the left
        return quickSelect(nums, low, pivot - 1, k - count);
    }
    void swap(int[] nums,int x,int y){
        int temp = nums[x];
        nums[x] = nums[y];
        nums[y] = temp;
    }