题目描述（中等难度）

找出第 k 大的数。

解法一 暴力

使用快排从大到小排序，将第 k 个数返回即可。

我们直接使用 java 提供的排序算法，又因为默认是从小到大排序，所以将倒数第 k 个数返回即可。

public int findKthLargest(int[] nums, int k) {
    Arrays.sort(nums);
    return nums[nums.length - k];
}

解法二

我们没必要把所有数字正确排序，我们可以借鉴快排中分区的思想，这里不细讲了，大家可以去回顾一下快排。

随机选择一个分区点，左边都是大于分区点的数，右边都是小于分区点的数。左部分的个数记做 m。

如果 k == m + 1，我们把分区点返回即可。

如果 k > m + 1，说明第 k 大数在右边，我们在右边去寻找第 k - m - 1 大的数即可。

如果 k < m + 1，说明第 k 大数在左边，我们在左边去寻找第 k 大的数即可。

左边和右边寻找在代码中采取递归即可。

分区达到的效果就是下边的样子。

原数组 3 7 6 1 5
如果把 5 作为分区点，那么数组最后就会变成下边的样子, i 指向最终的分区点
7 6 5 1 3
    ^
    i

代码的话，分区可以采取双指针，i 前边始终存比分区点大的元素。

public int findKthLargest(int[] nums, int k) {
    return findKthLargestHelper(nums, 0, nums.length - 1, k);
}
private int findKthLargestHelper(int[] nums, int start, int end, int k) {
    int i = start;
    int pivot = nums[end];//分区点
    //将 i 的左半部分存比分区点大的数
    //将 i 的右半部分存比分区点小的数
    for (int j = start; j < end; j++) {
        if (nums[j] >= pivot) {
            int temp = nums[i];
            nums[i] = nums[j];
            nums[j] = temp;
            i++;
        }
    }
    //分区点放到 i 的位置
    int temp = nums[i];
    nums[i] = pivot;
    nums[end] = temp;
    //左边的数量加上 1
    int count = i - start + 1;
    if (count == k) {
        return nums[i];
    //从右边去继续寻找
    } else if (count < k) {
        return findKthLargestHelper(nums, i + 1, end, k - count);
    //从左边去继续寻找    
    } else {
        return findKthLargestHelper(nums, start, i - 1, k);
    }
}

解法三

我们可以使用优先队列，建一个最大堆，然后依次弹出元素，弹出的第 k 个元素就是我们要找的。

优先队列的使用也不是第一次了，之前在 23 题 和 188 题 也用过，原理可以参考 这里 和 这里。

这里我们直接使用 java 提供的优先队列了。

public int findKthLargest(int[] nums, int k) {
    Comparator<Integer> cmp;
    cmp = new Comparator<Integer>() {
        @Override
        public int compare(Integer i1, Integer i2) {
            // TODO Auto-generated method stub
            return i2 - i1;
        }
    };
    // 建立最大堆
    Queue<Integer> q = new PriorityQueue<Integer>(cmp);
    for (int i = 0; i < nums.length; i++) {
        q.offer(nums[i]);
    }
    for (int i = 0; i < k - 1; i++) {
        q.poll();
    }
    return q.poll();
}

java 默认的是建最小堆，所以我们需要一个比较器来改变优先级。

如果使用最小堆也可以解决这个问题，只需要保证队列中一直是 k 个元素即可。当队列超出 k 个元素后，把队列中最小的去掉即可，这就保证了最后队列中的元素一定是前 k 大的元素。

public int findKthLargest(int[] nums, int k) {
    // 建立最小堆
    Queue<Integer> q = new PriorityQueue<Integer>();
    for (int i = 0; i < nums.length; i++) {
        q.offer(nums[i]);
        if (q.size() > k) {
            q.poll();
        }
    }
    return q.poll();
}

总

这道题不是很难，只要掌握了快排的思想，解法二也能很快写出来。解法三的话，就得事先了解优先队列了。

添加好友一起进步~

如果觉得有帮助的话，可以点击 这里 给一个 star 哦 ^^

如果想系统的学习数据结构和算法，强烈推荐一个我之前学过的课程，可以点击 这里 查看详情