leetcode.排序.215数组中的第k个最大元素-Java

1. 具体题目

在未排序的数组中找到第 k 个最大的元素。请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。

示例 :　　输入: [3,2,1,5,6,4] 和 k = 2　　输出: 5

2. 思路分析

方法一：最直接的方法是直接调用 Java 的排序方法 Arrays.sort，排序算法为快速排序，时间复杂度O(nlogn)

方法二：利用堆排序算法，维护一个大小等于 k 的小顶堆，最后取堆顶元素即可，可借助 Java 的数据结构 PriorityQueue（有序队列）

方法三：基于切分的快速选择，由于每次切分后都返回切分点下标值，所以可以找到下标为目标值的切分点，返回该切分点元素。

3. 代码

快速选择代码：

 public int findKthLargest(int[] nums, int k) {

         int target = nums.length - k;

         int l = 0, h = nums.length - 1;

         while(l < h){

             int index = partition(nums, l, h);

             if(target > index){

                 l = index + 1;

             }else if(target < index){

                 h = index - 1;

             }else{

                 return nums[target];

             }

         }

         return nums[target];

     }

     //切分算法

     private int partition(int[] nums, int l, int h){

         int flag = nums[l];

         while(l < h){

             while(nums[h] >= flag && l < h) h--;

             swap(nums, l, h);

             while(nums[l] <= flag && l < h) l++;

             swap(nums, l, h);

         }

         return l;

     }

     //元素交换

     private void swap(int[] nums, int i, int j){

         int temp = nums[i];

         nums[i] = nums[j];

         nums[j] = temp;

     }

巴特西

leetcode.排序.215数组中的第k个最大元素-Java

最新文章

热门文章