题意

Find the kth largest element in an unsorted array. Note that it is the kth 
largest element in the sorted order, not the kth distinct element.

样例

Input: [3,2,1,5,6,4] and k = 2
Output: 5
Input: [3,2,3,1,2,4,5,5,6] and k = 4
Output: 4

1. 解题思路

  这道题是一道非常典型的Top k问题，通常来说，Top k问题有两种比较通用的方法，一是大顶堆方法，可以维护一个大顶堆的数据结构，根据大顶堆的特性，我们可以很容易找到第k个元素；二是局部排序，维持k个元素的顺序。
  本文将简单的展示相关代码。介于Top k问题的解法比较通用，而且思想比较简单，本文就不做过多的分析。我们直接来看相关代码。

2. 代码

(1).大顶堆方法

    public int findKthLargest(int[] nums, int k) {
        PriorityQueue<Integer> queue = new PriorityQueue<>(k, new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                return o1.compareTo(o2);
            }
        });
        for (int i = 0; i < nums.length; i++) {
            queue.offer(nums[i]);
            if (queue.size() > k) {
                queue.poll();
            }
        }
        return queue.poll();
    }

(2).局部排序方法(这里以插入排序为例)

    public int findKthLargest(int[] nums, int k) {
        LinkedList<Integer> linkedList = new LinkedList<>();
        for (int i = 0; i < nums.length; i++) {
            if (linkedList.size() == 0) {
                linkedList.add(nums[i]);
            } else {
                if (nums[i] >= linkedList.getFirst()) {
                    linkedList.addFirst(nums[i]);
                } else if (nums[i] > linkedList.getLast()) {
                    for (int j = linkedList.size() - 1; j >= 1; j--) {
                        if (nums[i] >= linkedList.get(j) && nums[i] < linkedList.get(j - 1)) {
                            linkedList.add(j, nums[i]);
                        }
                    }
                } else {
                    linkedList.add(nums[i]);
                }
            }
            if (linkedList.size() > k) {
                linkedList.remove(linkedList.size() - 1);
            }
        }
        return linkedList.get(k - 1);
    }