力扣-215-Kth Element

评论

题目：
215. Kth Largest Element in an Array(medium)
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.

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

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

Note:
You may assume k is always valid, 1 ≤ k ≤ array’s length.

题目大意：
在未排序的数组中找到第 k 个最大的元素。请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。
注：你可以假设 k 总是有效的，且 1 ≤ k ≤ 数组的长度。

解题思路：
首先，最容易想到的就是先排序，然后按下标取出第k个最大元素。
其中，Arrays.sort(int[] nums)是将nums数组按升序排列(从小到大)，Arrays.sort(int[] nums,new Comparator())中重写Comparator中的compare方法就能将数组按降序排列(从大到小)，具体操作：
Java容器及其常用方法汇总、
java中Arrays.sort()的几种用法
或者升序排列但是从后往前输出也可以做到降序排列的效果。。

此外，同样可以利用堆排序，输出想要的结果。这里使用PriorityQueue优先队列，这里默认通过完全二叉树实现的小顶堆，关于大根堆的建堆、调整、插入、删除等操作说明，可以看这个序列——堆排序-大根堆(堆大顶)

官方题解中还提到了一种快速选择的方法，详情具体可以看官方题解方法二

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
Java:
//直接用Arrays的排序函数
//时间复杂度O(nlogn),空间复杂度O(1)
public int findKthLargest(int[] nums,int k){
    Arrays.sort(nums);
    return nums[nums.length - k];
}


//利用堆排序，构建一个小根堆
//时间复杂度O(NlogK),空间复杂度O(K)

//这种写法以及包含的思想相当重要，要牢牢掌握！

public int findKthLargest(int[] nums,int k){
    PriorityQueue<Integer> pq = new PriorityQueue<>();//小顶堆
    for(int val : nums){
       pq.offer(val); //会自动调整成小根堆
       if(pq.size() > k)//保证当前小顶堆中有k个比较后大的数
          pq.poll();
    }
    return pq.peek();//全部筛选后，选择堆顶的最小数
}


//快速选择
//时间复杂度O(N),空间复杂度O(1)
public int findKthLargest(int[] nums,int k){
    k = nums.length - k;
    int low = 0,high = nums.length - 1;
    while(low < high){
      int j = partition(nums,low,high);
      if(j == k)  break;
      else if(j < k)  low = j + 1;
      else  high = j - 1;
    }
    return nums[k];
}

private int partition(int[] a,int low,int high){
    int i = low,j = high + 1;
    while(true){
        while(a[++i] < a[low] && i < high);
        while(a[--j] > a[low] && j > low);
        if(i >= j)  break;
        swap(a,i,j);
    }
    swap(a,low,j);
    return j;
}

private void swap(int[] a,int i,int j){
    int t = a[i];
    a[i] = a[j];
    a[j] = t;
}

InstantCWeedStudent

个人简介。