215. 数组中的第K个最大元素(中等)twiceFor

Posted on In Views:

1，问题描述

215. 数组中的第K个最大元素

难度：中等

给定整数数组 nums 和整数 k，请返回数组中第 **k** 个最大的元素。

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

你必须设计并实现时间复杂度为 O(n) 的算法解决此问题。

示例 1:

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

示例 2:

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

提示：

  • 1 <= k <= nums.length <= 105
  • -104 <= nums[i] <= 104

2，初步思考

​ 这个文本本质就是排序，并且它还有时间复杂度的限制，稍微大一些就会超时！！！

3，代码处理

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
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
import java.util.Arrays;
import java.util.Comparator;
import java.util.PriorityQueue;

public class _215数组中的第K个最大元素 {

    int quickselect(int[] nums, int l, int r, int k) {
        if (l == r) return nums[k];
        int x = nums[l], i = l - 1, j = r + 1;
        while (i < j) {
            do i++; while (nums[i] < x);
            do j--; while (nums[j] > x);
            if (i < j) {
                int tmp = nums[i];
                nums[i] = nums[j];
                nums[j] = tmp;
            }
        }
        if (k <= j) return quickselect(nums, l, j, k);
        else return quickselect(nums, j + 1, r, k);
    }

    // 解法4:快速选择算法（官方）
    public int findKthLargest_gov(int[] _nums, int k) {
        int n = _nums.length;
        return quickselect(_nums, 0, n - 1, n - k);
    }

    //     解法3:快速选择算法（优化）,边界条件优化(超时限制！！！)
    public int findKthLargest_quick_select_v2(int[] nums, int k) {
        int left = 0;
        int right = nums.length;// 到大不了
        int target = nums.length - k;
        while (left <= right) {
            int index = left;
            for (int i = left + 1; i < right; i++) {
                if (nums[index] >= nums[i]) {
                    insertLeft(nums, index, i);
                    index++;
                }
            }
            if (index == target) {
                return nums[index];
            } else if (target < index) {
                right = index;
            } else {
                left = index + 1;
            }
        }
        return nums[nums.length - k];
    }

    private void insertLeft(int[] nums, int left, int right) {
        if (left + 1 == right) {
            swap(nums, left, right);
        } else {
            swap(nums, left, right);
            swap(nums, left + 1, right);
        }
    }

    // 解法3:快速选择
    public int findKthLargest_quick_select(int[] nums, int k) {
        int left = 1;
        int right = nums.length - 1;
        int index = 0;
        while (left <= right) {
            // 快速选择算法
            for (int i = left; i <= right; i++) {
                if (nums[index] > nums[i]) {
                    insertIndex(nums, index, i);
                    index++;
                }
            }

            // 后处理
            if (index == (nums.length - k)) {
                return nums[index];
            } else if (index < nums.length - k + 1) {
                index++;
                left = index + 1;
            } else {
                right = index - 1;
                index = 0;
                left = index + 1;
            }
        }
        return nums[nums.length - k];
    }

    private void insertIndex(int[] nums, int left, int right) {
        if (left + 1 == right) {
            swap(nums, left, right);
            return;
        }
        // 插入左边
        int temp = nums[left + 1];
        nums[left + 1] = nums[left];
        nums[left] = right;
        nums[right] = temp;
    }

    private void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }


    // 解法2:暴力破解，直接排序，选择第k大的元素，时间复杂度O(nlogn)
    public int findKthLargest_brute(int[] nums, int k) {
        Arrays.sort(nums);
        return nums[nums.length - k + 1];
    }

    // 解法1:堆heap，要求时间复杂度O(n)，那必然要用额外空间
    public int findKthLargest(int[] nums, int k) {
        PriorityQueue<Integer> heap = new PriorityQueue<>(Comparator.comparingInt(n -> n));
        for (int num : nums) {
            heap.offer(num);
            if (heap.size() > k) {
                heap.poll();
            }
        }
        return heap.poll();
    }

    public static void main(String[] args) {
        _215数组中的第K个最大元素 findKthLargest = new _215数组中的第K个最大元素();
//        System.out.println(findKthLargest.findKthLargest_quick_select_v2(new int[]{1,0,0,0,0,2,3,4,5}, 2));
//        System.out.println(findKthLargest.findKthLargest_quick_select_v2(new int[]{3, 2, 1, 5, 6, 4}, 2));
//        System.out.println(findKthLargest.findKthLargest_quick_select_v2(new int[]{7,6,5,4,3,2,1}, 2));
//        System.out.println(findKthLargest.findKthLargest_quick_select_v2(new int[]{1, 1}, 2));
        System.out.println(findKthLargest.findKthLargest_quick_select_v2(new int[]{3,3,3,3,4,3,3,3,3}, 1));
//        System.out.println(findKthLargest.findKthLargest_quick_select(new int[]{2, 1}, 2));
    }
}
/**
 * 第k个最大元素，本质就是排序，时间复杂度要求为O(n)
 * [3,2,1,5,6,4], k = 2,输出: 5
 * [3,2,1,4,5,6]
 * [3,2,1,4,5,6]
 * <p>
 * [1,2,3,4,5,6]
 * [3,2,8,1,9,_5_,6,7,4], k = 4,输出: 4
 * [2,3,8,1,9,_5_,6,7,4]
 * [2,1,3,8,9,5,6,7,4]
 * [2,1,3,5,6,7,4,8,9]
 */

参考链接：

https://leetcode.cn/problems/kth-largest-element-in-an-array/description/?envType=company&envId=bytedance&favoriteSlug=bytedance-thirty-days