0%

leetcode每日一题-数组中的第K个最大元素

Posted on Edited on In ,

数组中的第K个最大元素

image1

方法一：暴力法

可以先对数组进行排序，那么第k个最大元素的下标就应该为$n-k$（其中$n$为数组长度）。

1
class Solution {
2
    public int findKthLargest(int[] nums, int k) {
3
        int n = nums.length;
4
        Arrays.sort(nums);
5
        return nums[n-k];
6
    }
7
}

复杂度分析

  • 时间复杂度：$O(nlogn)$，排序使用的是快速排序，因此整体的时间复杂度就是快排的时间复杂度。
  • 空间复杂度：$O(1)$

方法二：基于快速排序的选择方法

快速排序是先选择一个中枢，然后遍历后面的元素，最终会把数组分为两部分，前面部分比中枢值小，后面部分大于或等于中枢值，如果交换之后中枢值所在的位置就是从后面数第k个，我们直接返回中枢值即可，如果从后面数大于第k个，我们只需按照同样的方式从后面部分开始找即可。如果从后面数小于第k个，我们同样从前面部分开始查找。这里为了防止出现最坏情况，即数据原本就是升序或者降序排列，使用随机化中枢的方式。

1
class Solution {
2
    Random random = new Random();
3
4
    public int findKthLargest(int[] nums, int k) {
5
        return quickSelect(nums, 0, nums.length - 1, k);
6
    }
7
8
    public int quickSelect(int[] nums, int l, int r, int k){
9
        int i = random.nextInt(r - l + 1) + l;
10
        swap(nums, i, r);
11
        int pivot = l;
12
        for (int j = l; j < r; j++) {
13
            if (nums[j] <= nums[r]) {
14
                swap(nums, pivot++, j);
15
            }
16
        }
17
        swap(nums, pivot, r);
18
        int count = r - pivot + 1;
19
        // 如果找到直接返回
20
        if (count == k)
21
            return nums[pivot];
22
        // 从右边部分找
23
        if (count > k)
24
            return quickSelect(nums, pivot + 1, r, k);
25
        // 从左边部分找
26
        return quickSelect(nums, l, pivot - 1, k - count);
27
    }
28
29
    public void swap(int[] a, int i, int j) {
30
        int temp = a[i];
31
        a[i] = a[j];
32
        a[j] = temp;
33
    }
34
}

复杂度分析

  • 时间复杂度：$O(n)$，因为这里使用了随机化来加速，参考《算法导论》9.2：期望为线性的选择算法。
  • 空间复杂度：$O(logn)$，递归使用栈空间的空间代价的期望为$O(logn)$。

方法三：基于堆排序的选择方法

我们也可以使用堆排序来解决这个问题——建立一个大根堆，做 $k-1$ 次删除操作后堆顶元素就是我们要找的答案。可以使用优先队列来实现，也可以自己实现建堆、调整、删除的过程。

优先队列实现：

1
import java.util.PriorityQueue;
2
3
public class Solution {
4
5
    public int findKthLargest(int[] nums, int k) {
6
        int len = nums.length;
7
        // 使用一个含有 len 个元素的最大堆，lambda 表达式应写成：(a, b) -> b - a
8
        PriorityQueue<Integer> maxHeap = new PriorityQueue<>(len, (a, b) -> b - a);
9
        for (int i = 0; i < len; i++) {
10
            maxHeap.add(nums[i]);
11
        }
12
        for (int i = 0; i < k - 1; i++) {
13
            maxHeap.poll();
14
        }
15
        return maxHeap.peek();
16
    }
17
}

自己实现：

1
class Solution {
2
    public int findKthLargest(int[] nums, int k) {
3
        int heapSize = nums.length;
4
        buildMaxHeap(nums, heapSize);
5
        for (int i = nums.length - 1; i >= nums.length - k + 1; --i) {
6
            swap(nums, 0, i);
7
            --heapSize;
8
            maxHeapify(nums, 0, heapSize);
9
        }
10
        return nums[0];
11
    }
12
13
    public void buildMaxHeap(int[] a, int heapSize) {
14
        for (int i = heapSize / 2; i >= 0; --i) {
15
            maxHeapify(a, i, heapSize);
16
        } 
17
    }
18
19
    public void maxHeapify(int[] a, int i, int heapSize) {
20
        int l = i * 2 + 1, r = i * 2 + 2, largest = i;
21
        if (l < heapSize && a[l] > a[largest]) {
22
            largest = l;
23
        } 
24
        if (r < heapSize && a[r] > a[largest]) {
25
            largest = r;
26
        }
27
        if (largest != i) {
28
            swap(a, i, largest);
29
            maxHeapify(a, largest, heapSize);
30
        }
31
    }
32
33
    public void swap(int[] a, int i, int j) {
34
        int temp = a[i];
35
        a[i] = a[j];
36
        a[j] = temp;
37
    }
38
}

复杂度分析

  • 时间复杂度：$O(nlogn)$，建堆的代价是$O(n)$，删除的总代价是$(klogn)$，因为$k<n$，所以渐进时间复杂为$O(nlogn)$。
  • 空间复杂度：$O(logn)$，递归使用栈空间的空间代价的期望为$O(logn)$。