Problem 215: Kth Largest Element in an Array

https://leetcode.com/problems/kth-largest-element-in-an-array/

思路

• 这道题可以用 heap 快速做出，但其并不是考点。

• 这道题的考点还是在 O(N) 的时间内，用额外 O(1) 的时间找出结果。所以我们考虑用 Quick Sort 的方法。

  
• 后面有两个版本，一个是用 sort 做的，另一个是用 heap 做的。heap 在 java 中用 PriorityQueue 实现。

public class Solution {
    public int findKthLargest(int[] nums, int k) {
        k = nums.length - k;
        int left = 0, right = nums.length - 1;
        while (left < right) {
            int position = partition(nums, left, right);
            if (position == k) {
                break;
            } else if (position < k) {
                left = position + 1;
            } else {
                right = position - 1;
            }
        }

        return nums[k];
    }

    private int partition(int[] nums, int left, int right) {
        int i = left;
        int j = right + 1;
        int pivot = nums[left];
        while (true) {
            while (i < right && nums[++i] < pivot);
            while (j > left && nums[--j] >= pivot);
            if (i >= j) {
                break;
            }
            swap(nums, i, j);
        }
        swap(nums, left, j);
        return j;
    }

    private void swap(int[] nums, int i, int j) {
        int tmp = nums[i];
        nums[i] = nums[j];
        nums[j] = tmp;
    }
}

/*
  sort version:
*/
public class Solution {
    public int findKthLargest(int[] nums, int k) {
        Arrays.sort(nums);
        int len = nums.length;

        return nums[len - k];
    }
}

/*
  heap version
*/
public class Solution {
    public int findKthLargest(int[] nums, int k) {
        PriorityQueue<Integer> heap = new PriorityQueue<Integer>();
        for (Integer i : nums) {
            heap.offer(i);
            if (heap.size() > k) {
                heap.poll();
            }
        }

        return heap.peek();
    }
}

易错点

1. 搞清第 k 大的意思

   k = nums.length - k;

2. 提前左右各向外移动一个位置，然后再往回逼近

   while (i < right && nums[++i] < pivot);
   while (j > left && nums[--j] >= pivot);

   第二个 while 是 >= 因为最后要找的是第 k 大的元素

3. swap，swap 的是 i，j 位置上的值

   // 第一次交换，pivot 两边的值交换
   swap(nums, i, j); 
   // 第二次是把 pivot 换到“大”组去
   swap(nums, left, j);
   // 找到 partition 位置
   return j;

   
4. 考虑好 left 和 right 的移动

   left = position + 1;

   right = position - 1;

   我当时写的是 left++和right--，很明显这是有问题的。position 决定的是第 k 个元素的精确位置，比他小的都在左边，比他大的都在右边。