LeetCode-215. 数组中的第K个最大元素-Java-medium

    /**
     * 交换数组中两个元素的位置
     *
     * @param nums
     * @param i
     * @param j
     */
    private void swap(int[] nums, int i, int j) {
        if (i != j) { // 两个相同的数^结果为0，开头加一个判断可以避免这种情况
            nums[i] ^= nums[j];
            nums[j] ^= nums[i];
            nums[i] ^= nums[j];
        }
    }

    /**
     * 随机选取主元，对区间[left, right]进行划分
     *
     * @param nums
     * @param left
     * @param right
     * @return
     */
    private int randPartition(int[] nums, int left, int right) {
        int random = new Random().nextInt(right - left + 1) + left; // 生成[left, right]内的随机数random
        swap(nums, left, random); // 交换nums[left]和nums[random]，即将随机选取的主元放在最前面
        int pivot = nums[left];   // 将随机选取的主元赋给pivot
        while (left < right) {
            while (left < right && nums[right] > pivot) { // 反复左移right
                right--;
            }
            nums[left] = nums[right]; // 将nums[right]挪到nums[left]
            while (left < right && nums[left] <= pivot) { // 反复右移left
                left++;
            }
            nums[right] = nums[left]; // 将nums[left]挪到nums[right]
        }
        nums[left] = pivot; // 把主元放到left和right相遇的地方
        return left; // 返回相遇的下标
    }

    /**
     * 随机选择算法 - 找第k个最大的数
     * 从nums[left, right]中找到第k个最大的数
     *
     * @param nums
     * @param left
     * @param right
     * @param k
     * @return
     */
    private int randSelect(int[] nums, int left, int right, int k) {
        if (left >= right) { // 边界
            return nums[left];
        }
        int pivotIndex = randPartition(nums, left, right);  // 划分后主元的位置
        int m = right - pivotIndex + 1; // nums[pivotIndex]是nums[left, right]中的第m个最大的数
        if (k > m) { // 第k个最大的数在主元左侧
            return randSelect(nums, left, pivotIndex - 1, k - m); // 到主元左侧去找第k-m个最大的数
        } else if (k < m) { // 第k个最大的数在主元右侧
            return randSelect(nums, pivotIndex + 1, right, k); // 到主元右侧去找第k个最大的数
        } else { // 找到了第k个最大的数
            return nums[pivotIndex];
        }
    }

    /**
     * 法一（随机选择算法 - 找第k个最大的数）
     * 1. 思路
     * （1）快速排序思想：先找到主元，把比它小的数据放在左边，比它大的数据放在右边，再递归对两个小的子序列进行排序
     * （2）本题是基于快速排序的应用，区别在于每一次只需要排序一边，直到找到下标为nums.length - k的元素
     * 2. 复杂度
     * （1）时间复杂度：O(n)
     * （2）空间复杂度：O(logn)
     * 3. 理解
     * （1）快排可以看成是二叉树，1分2，2分4......
     * （2）每一层都是O(n)的，一共有logn层，故快排时间复杂度是O(nlogn)
     * （3）这一题因为有个判断，可以每次快排时只对一边快排，故每一层的时间复杂度都是上一层的一半
     * （4）第一层n，第二层n/2，第三层n/4，共logn层。套用等比数列求和公式，可以得出O(n)
     * 4. 随机选取主元
     * （1）快排算法当序列中元素接近有序时会达到最坏时间复杂度O(n^2)
     * （2）产生原因是主元没有把当前区间划分为两个长度相近的子区间，故可以通过随机选取主元来解决
     *
     * @param nums
     * @param k
     * @return
     */
    public int findKthLargest(int[] nums, int k) {
        return randSelect(nums, 0, nums.length - 1, k); // 找第k个最大的数
    }
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

法二（随机选择算法 - 找第k大的数）

    /**
     * 交换数组中两个元素的位置
     *
     * @param nums
     * @param i
     * @param j
     */
    private void swap(int[] nums, int i, int j) {
        if (i != j) { // 两个相同的数^结果为0，开头加一个判断可以避免这种情况
            nums[i] ^= nums[j];
            nums[j] ^= nums[i];
            nums[i] ^= nums[j];
        }
    }

    /**
     * 随机选取主元，对区间[left, right]进行划分
     *
     * @param nums
     * @param left
     * @param right
     * @return
     */
    private int randPartition(int[] nums, int left, int right) {
        int random = new Random().nextInt(right - left + 1) + left; // 生成[left, right]内的随机数random
        swap(nums, left, random); // 交换nums[left]和nums[random]，即将随机选取的主元放在最前面
        int pivot = nums[left];   // 将随机选取的主元赋给pivot
        while (left < right) {
            while (left < right && nums[right] > pivot) { // 反复左移right
                right--;
            }
            nums[left] = nums[right]; // 将nums[right]挪到nums[left]
            while (left < right && nums[left] <= pivot) { // 反复右移left
                left++;
            }
            nums[right] = nums[left]; // 将nums[left]挪到nums[right]
        }
        nums[left] = pivot; // 把主元放到left和right相遇的地方
        return left; // 返回相遇的下标
    }

    /**
     * 随机选择算法 - 找第k大的数
     * 从nums[left, right]中找到第k大的数
     *
     * @param nums
     * @param left
     * @param right
     * @param k
     * @return
     */
    private void randSelect_2(int[] nums, int left, int right, int k) {
        if (left >= right) { // 边界
            return;
        }
        int pivotIndex = randPartition(nums, left, right);  // 划分后主元的位置
        if (k < pivotIndex) { // 第k大的数在主元左侧
            randSelect_2(nums, left, pivotIndex - 1, k); // 到主元左侧去找第k大的数
        } else if (k > pivotIndex) { // 第k大的数在主元右侧
            randSelect_2(nums, pivotIndex + 1, right, k); // 到主元右侧去找第k大的数
        } else { // 找到了第k大的数
            return;
        }
    }

    /**
     * 法二（随机选择算法 - 找第k大的数）
     * 1. 思路
     * （1）题目要找的是第k个最大的数，可以转换为找第nums.length - k大的数
     * 2. 复杂度
     * （1）时间复杂度：O(n)
     * （2）空间复杂度：O(logn)
     *
     * @param nums
     * @param k
     * @return
     */
    public int findKthLargest_2(int[] nums, int k) {
        randSelect_2(nums, 0, nums.length - 1, nums.length - k); // 找第nums.length - k大的数
        return nums[nums.length - k];
    }
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

法三（优先级队列）

    /**
     * 法三（优先级队列）
     * 固定优先级队列的长度为k，那么最后留在优先级队列里面的数就是最大的k个数
     *
     * @param nums
     * @param k
     * @return
     */
    public int findKthLargest_3(int[] nums, int k) {
        PriorityQueue<Integer> minHeap = new PriorityQueue<>(); // 默认小根堆
        for (int i = 0; i < k; i++) { // 建立一个K个数的小根堆
            minHeap.offer(nums[i]);
        }
        for (int i = k; i < nums.length; i++) {
            if (nums[i] > minHeap.peek()) {  // 如果接下来的数大于堆顶元素，就去掉堆顶元素，将这个大的数入堆
                minHeap.poll();
                minHeap.offer(nums[i]);
            }
        }
        return minHeap.peek(); // 堆顶的数就是第k大的
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

法四（计数排序）

    /**
     * 法四（计数排序）
     * 1. 概念
     * （1）计数排序是一个不需要比较的，类似于桶排序的线性时间排序算法
     * （2）计数排序的思想是在给定的一组序列中，先找出该序列中的最大值和最小值，
     * 从而确定需要开辟多大的辅助空间，每一个数在对应的辅助空间中都有唯一的下标
     * 2. 复杂度
     * （1）时间复杂度：O(n+k)，k为计数范围
     * （2）空间复杂度：O(k)
     * （3）稳定性：稳定
     * 3. 局限性
     * （1）当数列最大最小值差距过大时，并不适用于计数排序
     * （2）当数列元素不是整数时，并不适用于计数排序
     *
     * @param nums
     * @param k
     * @return
     */
    public int findKthLargest_4(int[] nums, int k) {
        int max = nums[0], min = nums[0];
        for (int num : nums) { // 找到最大值和最小值
            if (num > max) {
                max = num;
            }
            if (num < min) {
                min = num;
            }
        }
        int[] count = new int[max - min + 1]; // 根据最大值和最小值确定计数范围
        for (int num : nums) {
            count[num - min]++;
        }
        for (int i = max - min; i >= 0; i--) { // 寻找第k大的数字
            k -= count[i];
            if (k <= 0) {
                return min + i;
            }
        }
        return nums[0];
    }
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

法五_1（冒泡排序 - 递增）

    /**
     * 交换数组中两个元素的位置
     *
     * @param nums
     * @param i
     * @param j
     */
    private void swap(int[] nums, int i, int j) {
        if (i != j) { // 两个相同的数^结果为0，开头加一个判断可以避免这种情况
            nums[i] ^= nums[j];
            nums[j] ^= nums[i];
            nums[i] ^= nums[j];
        }
    }

    /**
     * 冒泡排序（递增排序）
     *
     * @param nums
     */
    private void bubbleSort_1(int[] nums) {
        int len = nums.length;
        boolean flag;
        for (int i = 0; i < len - 1; i++) {  // 进行性len-1趟排序
            flag = true;
            for (int j = 0; j < len - i - 1; j++) { // 遍历无序区
                if (nums[j] > nums[j + 1]) { // 将最大的元素移动到无序区末尾
                    swap(nums, j, j + 1);
                    flag = false;
                }
            }
            if (flag) { // 无序区中没有发生交换说明已经有序
                break;
            }
        }
    }

    /**
     * 法五_1（冒泡排序 - 递增）
     * 1. 思想
     * [无序区，有序区]，从无序区通过交换找出最大元素放到有序区前端
     * 2. 复杂度
     * （1）平均时间复杂度：O(n^2)
     * （2）最差时间复杂度：O(n^2)
     * （3）空间复杂度：O(1)
     * （4）稳定性：稳定
     *
     * @param nums
     * @param k
     * @return
     */
    public int findKthLargest_5_1(int[] nums, int k) {
        bubbleSort_1(nums);
        return nums[nums.length - k];
    }
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

法五_2（冒泡排序 - 递减）

    /**
     * 交换数组中两个元素的位置
     *
     * @param nums
     * @param i
     * @param j
     */
    private void swap(int[] nums, int i, int j) {
        if (i != j) { // 两个相同的数^结果为0，开头加一个判断可以避免这种情况
            nums[i] ^= nums[j];
            nums[j] ^= nums[i];
            nums[i] ^= nums[j];
        }
    }

    /**
     * 冒泡排序（递减排序）
     *
     * @param nums
     */
    private void bubbleSort_2(int[] nums) {
        int len = nums.length;
        boolean flag;
        for (int i = 0; i < len - 1; i++) {  // 进行性len-1趟排序
            flag = true;
            for (int j = 0; j < len - i - 1; j++) { // 遍历无序区
                if (nums[j] < nums[j + 1]) { // 将最小的元素移动到无序区末尾
                    swap(nums, j, j + 1);
                    flag = false;
                }
            }
            if (flag) { // 无序区中没有发生交换说明已经有序
                break;
            }
        }
    }

    /**
     * 法五_2（冒泡排序 - 递减）
     * 1. 思想
     * [无序区，有序区]，从无序区通过交换找出最小元素放到有序区前端
     * 2. 复杂度
     * （1）平均时间复杂度：O(n^2)
     * （2）最差时间复杂度：O(n^2)
     * （3）空间复杂度：O(1)
     * （4）稳定性：稳定
     *
     * @param nums
     * @param k
     * @return
     */
    public int findKthLargest_5_2(int[] nums, int k) {
        bubbleSort_2(nums);
        return nums[k - 1];
    }
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

法六_1（选择排序 - 递增）

    /**
     * 交换数组中两个元素的位置
     *
     * @param nums
     * @param i
     * @param j
     */
    private void swap(int[] nums, int i, int j) {
        if (i != j) { // 两个相同的数^结果为0，开头加一个判断可以避免这种情况
            nums[i] ^= nums[j];
            nums[j] ^= nums[i];
            nums[i] ^= nums[j];
        }
    }

    /**
     * 选择排序（递增排序）
     *
     * @param nums
     */
    private void selectSort_1(int[] nums) {
        int len = nums.length;
        for (int i = 0; i < len - 1; i++) { // 进行性len-1趟排序
            int min = i; // 初始为有序区末尾元素
            for (int j = i + 1; j < len; j++) { // 遍历无序区
                if (nums[j] < nums[min]) { // 找到[有序区末尾元素，无序区]中最小元素下标
                    min = j;
                }
            }
            if (i != min) { // i == min时也可以交换，不影响结果
                swap(nums, i, min); // 交换有序区末尾元素和[有序区末尾元素，无序区]中最小元素
            }
        }
    }

    /**
     * 法六_1（选择排序 - 递增）
     * 1. 思想
     * [有序区，无序区]，在无序区里找一个最小的元素跟在有序区的后面
     * 2. 复杂度
     * （1）平均时间复杂度：O(n^2)
     * （2）最差时间复杂度：O(n^2)
     * （3）空间复杂度：O(1)
     * （4）稳定性：数组不稳定、链表稳定
     *
     * @param nums
     * @param k
     * @return
     */
    public int findKthLargest_6_1(int[] nums, int k) {
        selectSort_1(nums);
        return nums[nums.length - k];
    }
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

法六_2（选择排序 - 递减）

    /**
     * 交换数组中两个元素的位置
     *
     * @param nums
     * @param i
     * @param j
     */
    private void swap(int[] nums, int i, int j) {
        if (i != j) { // 两个相同的数^结果为0，开头加一个判断可以避免这种情况
            nums[i] ^= nums[j];
            nums[j] ^= nums[i];
            nums[i] ^= nums[j];
        }
    }

    /**
     * 选择排序（递减排序）
     *
     * @param nums
     */
    private void selectSort_2(int[] nums) {
        int len = nums.length;
        for (int i = 0; i < len - 1; i++) { // 进行性len-1趟排序
            int max = i; // 初始为有序区末尾元素
            for (int j = i + 1; j < len; j++) { // 遍历无序区
                if (nums[j] > nums[max]) { // 找到[有序区末尾元素，无序区]中最大元素下标
                    max = j;
                }
            }
            if (i != max) { // i == min时也可以交换，不影响结果
                swap(nums, i, max); // 交换有序区末尾元素和[有序区末尾元素，无序区]中最大元素
            }
        }
    }

    /**
     * 法六_2（选择排序 - 递减）
     * 1. 思想
     * [有序区，无序区]，在无序区里找一个最大的元素跟在有序区的后面
     * 2. 复杂度
     * （1）平均时间复杂度：O(n^2)
     * （2）最差时间复杂度：O(n^2)
     * （3）空间复杂度：O(1)
     * （4）稳定性：数组不稳定、链表稳定
     *
     * @param nums
     * @param k
     * @return
     */
    public int findKthLargest_6_2(int[] nums, int k) {
        selectSort_2(nums);
        return nums[k - 1];
    }
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

法七_1（插入排序 - 递增）

    /**
     * 插入排序（递增排序）
     * 针对有序序列在插入时采用移动法
     *
     * @param nums
     */
    private void insertSort_1(int[] nums) {
        int len = nums.length;
        for (int i = 1; i < len; i++) { // 有序区从前往后扩张
            int insert = nums[i]; // insert为无序区第一个元素
            for (int j = i - 1; j >= 0; j--) { // 从后往前遍历有序区
                if (insert < nums[j]) { // insert小于前一个元素
                    nums[j + 1] = nums[j]; // 将nums[j]后移一位覆盖nums[j + 1]
                    nums[j] = insert; // insert插入原来nums[j]的位置
                } else { // insert大于前一个的元素，insert保持原来位置即可
                    break;
                }
            }
        }
    }

    /**
     * 法七_1（插入排序 - 递增）
     * 1. 思想
     * [有序区，无序区]，把无序区的第一个元素插入到有序区的合适的位置
     * 2. 复杂度
     * （1）平均时间复杂度：O(n^2)
     * （2）最差时间复杂度：O(n^2)
     * （3）空间复杂度：O(1)
     * （4）稳定性：稳定
     *
     * @param nums
     * @param k
     * @return
     */
    public int findKthLargest_7_1(int[] nums, int k) {
        insertSort_1(nums);
        return nums[nums.length - k];
    }
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

法七_2（插入排序 - 递减）

    /**
     * 插入排序（递减排序）
     * 针对有序序列在插入时采用移动法
     *
     * @param nums
     */
    private void insertSort_2(int[] nums) {
        int len = nums.length;
        for (int i = 1; i < len; i++) { // 有序区从前往后扩张
            int insert = nums[i]; // insert为无序区第一个元素
            for (int j = i - 1; j >= 0; j--) { // 从后往前遍历有序区
                if (insert > nums[j]) { // insert大于前一个元素
                    nums[j + 1] = nums[j]; // 将nums[j]后移一位覆盖nums[j + 1]
                    nums[j] = insert; // insert插入原来nums[j]的位置
                } else { // insert小于前一个的元素，insert保持原来位置即可
                    break;
                }
            }
        }
    }

    /**
     * 法七_2（插入排序 - 递减）
     * 1. 思想
     * [有序区，无序区]，把无序区的第一个元素插入到有序区的合适的位置
     * 2. 复杂度
     * （1）平均时间复杂度：O(n^2)
     * （2）最差时间复杂度：O(n^2)
     * （3）空间复杂度：O(1)
     * （4）稳定性：稳定
     *
     * @param nums
     * @param k
     * @return
     */
    public int findKthLargest_7_2(int[] nums, int k) {
        insertSort_2(nums);
        return nums[k - 1];
    }
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

法八_1（快速排序 - 递增）

    /**
     * 交换数组中两个元素的位置
     *
     * @param nums
     * @param i
     * @param j
     */
    private void swap(int[] nums, int i, int j) {
        if (i != j) { // 两个相同的数^结果为0，开头加一个判断可以避免这种情况
            nums[i] ^= nums[j];
            nums[j] ^= nums[i];
            nums[i] ^= nums[j];
        }
    }

    /**
     * 快速排序（递增排序）
     *
     * @param nums
     * @param left
     * @param right
     */
    private void quickSort_1(int[] nums, int left, int right) {
        if (left < right) {
            int pivot = left; // 简便起见，默认以第一个元素作为主元
            int index = left + 1; // index指向[小数]区间最后一个元素下标
            for (int i = index; i <= right; i++) {
                if (nums[i] < nums[pivot]) { // 比主元小的元素都交换至[小数]区间
                    swap(nums, index, i);
                    index++;
                }
            }
            swap(nums, index - 1, pivot); // 将主元和[小数]区间最后一位元素交换位置
            pivot = index - 1; // 主元下标
            quickSort_1(nums, left, pivot - 1); // 对[小数]区间进行快排
            quickSort_1(nums, pivot + 1, right); // 对[大数]区间进行快排
        }
    }

    /**
     * 法八_1（快速排序 - 递增）
     * 1. 思想
     * [小数，基准元素，大数]，在区间中随机挑选一个元素作基准，将小于基准的元素放在基准之前，
     * 大于基准的元素放在基准之后，再分别对小数区与大数区进行排序
     * 2. 复杂度
     * （1）平均时间复杂度：O(nlogn)
     * （2）最差时间复杂度：O(n^2)
     * （3）空间复杂度：O(logn)
     * （4）稳定性：不稳定
     *
     * @param nums
     * @param k
     * @return
     */
    public int findKthLargest_8_1(int[] nums, int k) {
        quickSort_1(nums, 0, nums.length - 1);
        return nums[nums.length - k];
    }
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

法八_2（快速排序 - 递减）

    /**
     * 交换数组中两个元素的位置
     *
     * @param nums
     * @param i
     * @param j
     */
    private void swap(int[] nums, int i, int j) {
        if (i != j) { // 两个相同的数^结果为0，开头加一个判断可以避免这种情况
            nums[i] ^= nums[j];
            nums[j] ^= nums[i];
            nums[i] ^= nums[j];
        }
    }

    /**
     * 快速排序（递减排序）
     *
     * @param nums
     * @param left
     * @param right
     */
    private void quickSort_2(int[] nums, int left, int right) {
        if (left < right) {
            int pivot = left; // 简便起见，默认以第一个元素作为主元
            int index = left + 1; // index指向[大数]区间最后一个元素下标
            for (int i = index; i <= right; i++) {
                if (nums[i] > nums[pivot]) { // 比主元大的元素都交换至[大数]区间
                    swap(nums, index, i);
                    index++;
                }
            }
            swap(nums, index - 1, pivot); // 将主元和[大数]区间最后一位元素交换位置
            pivot = index - 1; // 主元下标
            quickSort_2(nums, left, pivot - 1); // 对[大数]区间进行快排
            quickSort_2(nums, pivot + 1, right); // 对[小数]区间进行快排
        }
    }

    /**
     * 法八_2（快速排序 - 递减）
     * 1. 思想
     * [大数，基准元素，小数]，在区间中随机挑选一个元素作基准，将大于基准的元素放在基准之前，
     * 小于基准的元素放在基准之后，再分别对大数区与小数区进行排序
     * 2. 复杂度
     * （1）平均时间复杂度：O(nlogn)
     * （2）最差时间复杂度：O(n^2)
     * （3）空间复杂度：O(logn)
     * （4）稳定性：不稳定
     *
     * @param nums
     * @param k
     * @return
     */
    public int findKthLargest_8_2(int[] nums, int k) {
        quickSort_2(nums, 0, nums.length - 1);
        return nums[k - 1];
    }
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

法九_1（堆排序 - 最大堆）

    /**
     * 交换数组中两个元素的位置
     *
     * @param nums
     * @param i
     * @param j
     */
    private void swap(int[] nums, int i, int j) {
        if (i != j) { // 两个相同的数^结果为0，开头加一个判断可以避免这种情况
            nums[i] ^= nums[j];
            nums[j] ^= nums[i];
            nums[i] ^= nums[j];
        }
    }

    /**
     * 对nums数组在[low, high]范围进行向下调整
     * 时间复杂度：O(logn)
     *
     * @param nums
     * @param low
     * @param high
     */
    private void downAdjust_1(int[] nums, int low, int high) {
        int dad = low, son = dad * 2 + 1; // dad为欲调整节点下标，son为其左孩子下标
        while (son <= high) { // 存在孩子节点
            if (son + 1 <= high && nums[son + 1] > nums[son]) { // 右孩子存在且右孩子大于左孩子
                son++; // son指向右孩子下标
            }
            if (nums[son] > nums[dad]) { // 左右孩子中最大者比欲调整节点大
                swap(nums, son, dad); // 欲调整节点和左右孩子中最大者交换位置
                dad = son; // dad指向欲调整节点最新位置
                son = dad * 2 + 1; // son指向欲调整节点最新位置左孩子下标
            } else { // 左右孩子中最大者比欲调整节点小，调整结束
                break;
            }
        }
    }

    /**
     * 建最大堆
     * （1）完全二叉树叶子节点个数为len/2，因此数组下标在[0, len/2-1]范围内的节点都是非叶子节点
     * （2）故可以从len/2-1开始倒着枚举节点
     * 时间复杂度：O(n)
     *
     * @param nums
     * @param len
     */
    private void createMaxHeap(int[] nums, int len) {
        for (int i = len / 2 - 1; i >= 0; i--) { // 从后往前遍历非叶子节点
            downAdjust_1(nums, i, len - 1);
        }
    }

    /**
     * 法九_1（堆排序 - 最大堆）
     * 1. 思想
     * [最大堆，有序区]，从堆顶把根拿出来放在有序区之前，再恢复堆
     * 2. 复杂度
     * （1）平均时间复杂度：O(nlogn)
     * （2）最差时间复杂度：O(nlogn)
     * （3）空间复杂度：O(1)
     * （4）稳定性：不稳定
     *
     * @param nums
     * @param k
     * @return
     */
    public int findKthLargest_9_1(int[] nums, int k) {
        int len = nums.length;
        createMaxHeap(nums, len); // 建最大堆
        for (int i = len - 1; i > 0; i--) { // 从后往前遍历，直到堆中只剩一个元素
            swap(nums, i, 0);  // 交换最大堆中最后一个元素nums[i]与堆顶nums[0]
            downAdjust_1(nums, 0, i - 1); // 堆中元素减1，调整堆顶
        }
        return nums[nums.length - k];
    }
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

法九_2（堆排序 - 最小堆）

    /**
     * 交换数组中两个元素的位置
     *
     * @param nums
     * @param i
     * @param j
     */
    private void swap(int[] nums, int i, int j) {
        if (i != j) { // 两个相同的数^结果为0，开头加一个判断可以避免这种情况
            nums[i] ^= nums[j];
            nums[j] ^= nums[i];
            nums[i] ^= nums[j];
        }
    }

    /**
     * 对nums数组在[low, high]范围进行向下调整
     * 时间复杂度：O(logn)
     *
     * @param nums
     * @param low
     * @param high
     */
    private void downAdjust_2(int[] nums, int low, int high) {
        int dad = low, son = dad * 2 + 1; // dad为欲调整节点下标，son为其左孩子下标
        while (son <= high) { // 存在孩子节点
            if (son + 1 <= high && nums[son + 1] < nums[son]) { // 右孩子存在且右孩子小于左孩子
                son++; // son指向右孩子下标
            }
            if (nums[son] < nums[dad]) { // 左右孩子中最小者比欲调整节点小
                swap(nums, son, dad); // 欲调整节点和左右孩子中最小者交换位置
                dad = son; // dad指向欲调整节点最新位置
                son = dad * 2 + 1; // son指向欲调整节点最新位置左孩子下标
            } else { // 左右孩子中最小者比欲调整节点大，调整结束
                break;
            }
        }
    }

    /**
     * 建最小堆
     * （1）完全二叉树叶子节点个数为len/2，因此数组下标在[0, len/2-1]范围内的节点都是非叶子节点
     * （2）故可以从len/2-1开始倒着枚举节点
     * 时间复杂度：O(n)
     *
     * @param nums
     * @param len
     */
    private void createMinHeap(int[] nums, int len) {
        for (int i = len / 2 - 1; i >= 0; i--) { // 从后往前遍历非叶子节点
            downAdjust_2(nums, i, len - 1);
        }
    }

    /**
     * 法九_2（堆排序 - 最小堆）
     * 1. 思想
     * [最小堆，有序区]，从堆顶把根拿出来放在有序区之前，再恢复堆
     * 2. 复杂度
     * （1）平均时间复杂度：O(nlogn)
     * （2）最差时间复杂度：O(nlogn)
     * （3）空间复杂度：O(1)
     * （4）稳定性：不稳定
     *
     * @param nums
     * @param k
     * @return
     */
    public int findKthLargest_9_2(int[] nums, int k) {
        int len = nums.length;
        createMinHeap(nums, len); // 建最小堆
        for (int i = len - 1; i > 0; i--) { // 从后往前遍历，直到堆中只剩一个元素
            swap(nums, i, 0);  // 交换最小堆中最后一个元素nums[i]与堆顶nums[0]
            downAdjust_2(nums, 0, i - 1); // 堆中元素减1，调整堆顶
        }
        return nums[k - 1];
    }
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

法十_1（归并排序 - 递增）

    /**
     * 将递增区间nums[l1, r1]与nums[l2, r2]合并为递增区间
     * l1 = left, r1 = mid, l2 = mid + 1, r2 = right
     *
     * @param nums
     * @param left
     * @param mid
     * @param right
     */
    private void merge_1(int[] nums, int left, int mid, int right) {
        int i = left, j = mid + 1, index = 0;   // i指向nums[l1]，j指向nums[l2]
        int[] temp = new int[right - left + 1]; // temp临时存放合并后的数组，index为其下标
        while (i <= mid && j <= right) { // 遍历nums[l1, r1]和nums[l2, r2]公共长度部分
            temp[index++] = nums[i] < nums[j] ? nums[i++] : nums[j++]; // 将较小的元素放前面
        }
        while (i <= mid) {   // 将nums[l1, r1]剩余元素加入temp
            temp[index++] = nums[i++];
        }
        while (j <= right) { // 将nums[l2, r2]剩余元素加入temp
            temp[index++] = nums[j++];
        }
        for (int num : temp) {
            nums[left++] = num; // 将合并后的序列temp赋值回nums
        }
    }

    /**
     * 归并排序（递增排序）
     */
    private void mergeSort_1(int[] nums, int left, int right) {
        if (left < right) {
            int mid = left + (right - left) / 2; // 取[left, right]中点
            mergeSort_1(nums, left, mid); // 左子区间归并排序
            mergeSort_1(nums, mid + 1, right); // 右子区间归并排序
            merge_1(nums, left, mid, right); // 将左子区间和右子区间合并
        }
    }

    /**
     * 法十_1（归并排序 - 递增）
     * 1. 思想
     * 归并排序的核心在于将两个有序序列合并为一个有序序列
     * 2. 复杂度
     * （1）平均时间复杂度：O(nlogn)
     * （2）最差时间复杂度：O(nlogn)
     * （3）空间复杂度：O(n)
     * （4）稳定性：稳定
     *
     * @param nums
     * @param k
     * @return
     */
    public int findKthLargest_10_1(int[] nums, int k) {
        mergeSort_1(nums, 0, nums.length - 1);
        return nums[nums.length - k];
    }
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

法十_2（归并排序 - 递减）

    /**
     * 将递减区间nums[l1, r1]与nums[l2, r2]合并为递减区间
     * l1 = left, r1 = mid, l2 = mid + 1, r2 = right
     *
     * @param nums
     * @param left
     * @param mid
     * @param right
     */
    private void merge_2(int[] nums, int left, int mid, int right) {
        int i = left, j = mid + 1, index = 0;   // i指向nums[l1]，j指向nums[l2]
        int[] temp = new int[right - left + 1]; // temp临时存放合并后的数组，index为其下标
        while (i <= mid && j <= right) { // 遍历nums[l1, r1]和nums[l2, r2]公共长度部分
            temp[index++] = nums[i] > nums[j] ? nums[i++] : nums[j++]; // 将较大的元素放前面
        }
        while (i <= mid) {   // 将nums[l1, r1]剩余元素加入temp
            temp[index++] = nums[i++];
        }
        while (j <= right) { // 将nums[l2, r2]剩余元素加入temp
            temp[index++] = nums[j++];
        }
        for (int num : temp) {
            nums[left++] = num; // 将合并后的序列temp赋值回nums
        }
    }

    /**
     * 归并排序（递减排序）
     */
    private void mergeSort_2(int[] nums, int left, int right) {
        if (left < right) {
            int mid = left + (right - left) / 2; // 取[left, right]中点
            mergeSort_2(nums, left, mid); // 左子区间归并排序
            mergeSort_2(nums, mid + 1, right); // 右子区间归并排序
            merge_2(nums, left, mid, right); // 将左子区间和右子区间合并
        }
    }

    /**
     * 法十_2（归并排序 - 递减）
     * 1. 思想
     * 归并排序的核心在于将两个有序序列合并为一个有序序列
     * 2. 复杂度
     * （1）平均时间复杂度：O(nlogn)
     * （2）最差时间复杂度：O(nlogn)
     * （3）空间复杂度：O(n)
     * （4）稳定性：稳定
     *
     * @param nums
     * @param k
     * @return
     */
    public int findKthLargest_10_2(int[] nums, int k) {
        mergeSort_2(nums, 0, nums.length - 1);
        return nums[k - 1];
    }
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

法十一_1（希尔排序 - 递增）

    /**
     * 交换数组中两个元素的位置
     *
     * @param nums
     * @param i
     * @param j
     */
    private void swap(int[] nums, int i, int j) {
        if (i != j) { // 两个相同的数^结果为0，开头加一个判断可以避免这种情况
            nums[i] ^= nums[j];
            nums[j] ^= nums[i];
            nums[i] ^= nums[j];
        }
    }

    /**
     * 希尔排序（递增排序）
     * （1）针对有序序列在插入时采用交换法
     * （2）选择增量gap=len/2，缩小增量继续以gap=gap/2的方式
     * （3）{n/2, (n/2)/2, ..., 1}，称为增量序列
     *
     * @param nums
     */
    private void shellSort_1(int[] nums) {
        int len = nums.length;
        for (int gap = len / 2; gap > 0; gap /= 2) {
            for (int i = gap; i < len; i++) { // 有序区从前往后扩张
                for (int j = i - gap; j >= 0; j -= gap) { // 从后往前遍历有序区
                    if (nums[j + gap] < nums[j]) { // 欲插入元素小于前一位元素
                        swap(nums, j, j + gap); // 交换二者位置
                    }
                }
            }
        }
    }

    /**
     * 法十一_1（希尔排序 - 递增）
     * 1. 思想
     * 每一轮按照事先决定的间隔进行插入排序，间隔会依次缩小，最后一次一定要是1
     * 2. 复杂度
     * （1）平均时间复杂度：O(n(logn)^2)
     * （2）最差时间复杂度：O(n^2)
     * （3）空间复杂度：O(1)
     * （4）稳定性：不稳定
     *
     * @param nums
     * @param k
     * @return
     */
    public int findKthLargest_11_1(int[] nums, int k) {
        shellSort_1(nums);
        return nums[nums.length - k];
    }
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

法十一_2（希尔排序 - 递减）

    /**
     * 交换数组中两个元素的位置
     *
     * @param nums
     * @param i
     * @param j
     */
    private void swap(int[] nums, int i, int j) {
        if (i != j) { // 两个相同的数^结果为0，开头加一个判断可以避免这种情况
            nums[i] ^= nums[j];
            nums[j] ^= nums[i];
            nums[i] ^= nums[j];
        }
    }

    /**
     * 希尔排序（递减排序）
     * （1）针对有序序列在插入时采用交换法
     * （2）选择增量gap=len/2，缩小增量继续以gap=gap/2的方式
     * （3）{n/2, (n/2)/2, ..., 1}，称为增量序列
     *
     * @param nums
     */
    private void shellSort_2(int[] nums) {
        int len = nums.length;
        for (int gap = len / 2; gap > 0; gap /= 2) {
            for (int i = gap; i < len; i++) { // 有序区从前往后扩张
                for (int j = i - gap; j >= 0; j -= gap) { // 从后往前遍历有序区
                    if (nums[j + gap] > nums[j]) { // 欲插入元素大于前一位元素
                        swap(nums, j, j + gap); // 交换二者位置
                    }
                }
            }
        }
    }

    /**
     * 法十一_2（希尔排序 - 递减）
     * 1. 思想
     * 每一轮按照事先决定的间隔进行插入排序，间隔会依次缩小，最后一次一定要是1
     * 2. 复杂度
     * （1）平均时间复杂度：O(n(logn)^2)
     * （2）最差时间复杂度：O(n^2)
     * （3）空间复杂度：O(1)
     * （4）稳定性：不稳定
     *
     * @param nums
     * @param k
     * @return
     */
    public int findKthLargest_11_2(int[] nums, int k) {
        shellSort_2(nums);
        return nums[k - 1];
    }
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

法十二_1（计数排序 - 递增）

    /**
     * 计数排序（递增排序）
     * 计数排序不是比较排序，排序的速度快于任何比较排序算法
     *
     * @param nums
     */
    private void countSort_1(int[] nums) {
        int max = nums[0], min = nums[0];
        for (int num : nums) { // 找到最大值和最小值
            if (num > max) {
                max = num;
            }
            if (num < min) {
                min = num;
            }
        }
        int[] count = new int[max - min + 1]; // 根据最大值和最小值确定计数范围
        for (int num : nums) { // 开始计数
            count[num - min]++;
        }
        int k = 0;
        for (int i = 0; i < count.length; i++) { // 从前往后遍历count数组，替换掉nums数组
            for (int j = 0; j < count[i]; j++) {
                nums[k++] = min + i;
            }
        }
    }

    /**
     * 法十二_1（计数排序 - 递增）
     * 1. 思想
     * 在给定的一组序列中，先找出该序列中的最大值和最小值，从而确定需要开辟多大的辅助空间，
     * 每一个数在对应的辅助空间中都有唯一的下标
     * 2. 复杂度
     * （1）平均时间复杂度：O(n+m)
     * （2）最差时间复杂度：O(n+m)
     * （3）空间复杂度：O(m)
     * （4）稳定性：稳定
     * m：代表计数范围
     *
     * @param nums
     * @param k
     * @return
     */
    public int findKthLargest_12_1(int[] nums, int k) {
        countSort_1(nums);
        return nums[nums.length - k];
    }
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

法十二_2（计数排序 - 递减）

    /**
     * 计数排序（递减排序）
     * 计数排序不是比较排序，排序的速度快于任何比较排序算法
     *
     * @param nums
     */
    private void countSort_2(int[] nums) {
        int max = nums[0], min = nums[0];
        for (int num : nums) { // 找到最大值和最小值
            if (num > max) {
                max = num;
            }
            if (num < min) {
                min = num;
            }
        }
        int[] count = new int[max - min + 1]; // 根据最大值和最小值确定计数范围
        for (int num : nums) { // 开始计数
            count[num - min]++;
        }
        int k = 0;
        for (int i = count.length - 1; i >= 0; i--) { // 从后往前遍历count数组，替换掉nums数组
            for (int j = 0; j < count[i]; j++) {
                nums[k++] = min + i;
            }
        }
    }

    /**
     * 法十二_2（计数排序 - 递减）
     * 1. 思想
     * 在给定的一组序列中，先找出该序列中的最大值和最小值，从而确定需要开辟多大的辅助空间，
     * 每一个数在对应的辅助空间中都有唯一的下标
     * 2. 复杂度
     * （1）平均时间复杂度：O(n+m)
     * （2）最差时间复杂度：O(n+m)
     * （3）空间复杂度：O(m)
     * （4）稳定性：稳定
     * m：代表计数范围
     *
     * @param nums
     * @param k
     * @return
     */
    public int findKthLargest_12_2(int[] nums, int k) {
        countSort_2(nums);
        return nums[k - 1];
    }
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

法十三_1（桶排序 - 递增）

    /**
     * 桶排序（递增排序）
     *
     * @param nums
     */
    private void bucketSort_1(int[] nums) {
        int len = nums.length;
        int max = nums[0], min = nums[0];
        for (int num : nums) { // 找到最大值和最小值
            if (num > max) {
                max = num;
            }
            if (num < min) {
                min = num;
            }
        }
        int gap = (max - min) / len + 1; // 确定桶的跨度大小
        int bucketNum = (max - min) / gap + 1; // 确定桶的个数
        List<List<Integer>> bucketList = new ArrayList<>(); // 创建一组桶
        for (int i = 0; i < bucketNum; i++) { // 初始化每个桶
            bucketList.add(new LinkedList<>());
        }
        for (int i = 0; i < nums.length; i++) { // 遍历数组，将数据放入对应桶中
            bucketList.get((nums[i] - min) / gap).add(nums[i]);
        }
        for (int i = 0; i < bucketList.size(); i++) { // 对每个桶内部从小到大进行排序
            Collections.sort(bucketList.get(i)); // 底层采用了归并排序的优化版本
        }
        int k = 0;
        for (int i = 0; i < bucketNum; i++) { // 把每个桶排序好的数据进行合并汇总放回原数组
            for (Integer num : bucketList.get(i)) {
                nums[k++] = num;
            }
        }
    }

    /**
     * 法十三_1（桶排序 - 递增）
     * 1. 思想
     * 将最大值和最小值之间的元素进行瓜分，设定某个桶的容量，然后再定义每个桶的跨度，然后根据元素的大小范围，
     * 将他们放入各自的桶中，再对每个桶进行排序，最后按顺序输出所有桶中元素
     * 2. 复杂度
     * （1）平均时间复杂度：O(n+m)
     * （2）最差时间复杂度：O(n^2)
     * （3）空间复杂度：O(n+m)
     * （4）稳定性：稳定
     * m：代表计数范围
     *
     * @param nums
     * @param k
     * @return
     */
    public int findKthLargest_13_1(int[] nums, int k) {
        bucketSort_1(nums);
        return nums[nums.length - k];
    }
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

法十三_2（桶排序 - 递减）

    /**
     * 桶排序（递减排序）
     *
     * @param nums
     */
    private void bucketSort_2(int[] nums) {
        int len = nums.length;
        int max = nums[0], min = nums[0];
        for (int num : nums) { // 找到最大值和最小值
            if (num > max) {
                max = num;
            }
            if (num < min) {
                min = num;
            }
        }
        int gap = (max - min) / len + 1; // 确定桶的跨度大小
        int bucketNum = (max - min) / gap + 1; // 确定桶的个数
        List<List<Integer>> bucketList = new ArrayList<>(); // 创建一组桶
        for (int i = 0; i < bucketNum; i++) { // 初始化每个桶
            bucketList.add(new LinkedList<>());
        }
        for (int i = 0; i < nums.length; i++) { // 遍历数组，将数据放入对应桶中
            bucketList.get((nums[i] - min) / gap).add(nums[i]);
        }
        for (int i = 0; i < bucketList.size(); i++) { // 对每个桶内部从大到小进行排序
            Collections.sort(bucketList.get(i), Collections.reverseOrder()); // 底层采用了归并排序的优化版本
        }
        int k = 0;
        for (int i = bucketNum - 1; i >= 0; i--) { // 把每个桶排序好的数据进行合并汇总放回原数组
            for (Integer num : bucketList.get(i)) {
                nums[k++] = num;
            }
        }
    }

    /**
     * 法十三_2（桶排序 - 递减）
     * 1. 思想
     * 将最大值和最小值之间的元素进行瓜分，设定某个桶的容量，然后再定义每个桶的跨度，然后根据元素的大小范围，
     * 将他们放入各自的桶中，再对每个桶进行排序，最后按顺序输出所有桶中元素
     * 2. 复杂度
     * （1）平均时间复杂度：O(n+m)
     * （2）最差时间复杂度：O(n^2)
     * （3）空间复杂度：O(n+m)
     * （4）稳定性：稳定
     * m：代表计数范围
     *
     * @param nums
     * @param k
     * @return
     */
    public int findKthLargest_13_2(int[] nums, int k) {
        bucketSort_2(nums);
        return nums[k - 1];
    }
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

法十四_1（基数排序 - 递增）

    /**
     * 基数排序（递增排序）
     * （1）所有数字都是由0~9组成，因此需要10个桶来排序
     * （2）暂时无法处理负数
     *
     * @param nums
     */
    private void radixSort_1(int[] nums) {
        int len = nums.length;
        int max = nums[0];
        for (int num : nums) { // 找到最大数
            if (num > max) {
                max = num;
            }
        }
        int digit = 0;
        while (max != 0) { // 获取最大数的位数
            max /= 10;
            digit++;
        }
        int bucketNum = 10; // 创建10个桶
        List<List<Integer>> bucketList = new ArrayList<>();
        for (int i = 0; i < bucketNum; i++) { // 初始化每个桶
            bucketList.add(new LinkedList<>());
        }
        for (int i = 0; i < digit; i++) { // 按最低位优先依次对各关键字进行分配和收集
            for (int j = 0; j < len; j++) { // 第i趟分配
                int radix = (int) (nums[j] / Math.pow(10, i)) % 10; // 获取当前数字第i位的数
                bucketList.get(radix).add(nums[j]); // 放进对应的桶里
            }
            int k = 0;
            for (List<Integer> bucket : bucketList) { // 第i趟收集，按第i位从小到大的顺序将num排序
                for (Integer num : bucket) {
                    nums[k++] = num;
                }
                bucket.clear(); // 将每个桶都清空，供下一次分配和收集使用
            }
        }
    }

    /**
     * 法十四_1（基数排序 - 递增）
     * 1. 思想
     * 按位数从低到高分配到桶中，有多少位分配多少次，分配完成后，从低位到高位依次取出
     * 2. 复杂度
     * （1）平均时间复杂度：O(n*k)
     * （2）最差时间复杂度：O(n*k)
     * （3）空间复杂度：O(n+k)
     * （4）稳定性：稳定
     * k：代表数值中的"数位"个数
     * 3. 优缺点
     * （1）优点：在数字位数相差不大的情况下具有较高效率，如[345, 652, 984, 439]，都是三位数，需要分配+收集三次
     * （2）缺点：在数字位数差距非常大时，效率低下，如[1，999999999999999]，需要分配+收集m次，m为较大数字的位数
     *
     * @param nums
     * @param k
     * @return
     */
    public int findKthLargest_14_1(int[] nums, int k) {
        radixSort_1(nums);
        return nums[nums.length - k];
    }
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

法十四_2（基数排序 - 递减）

    /**
     * 基数排序（递减排序）
     * （1）所有数字都是由0~9组成，因此需要10个桶来排序
     * （2）暂时无法处理负数
     *
     * @param nums
     */
    private void radixSort_2(int[] nums) {
        int len = nums.length;
        int max = nums[0];
        for (int num : nums) { // 找到最大数
            if (num > max) {
                max = num;
            }
        }
        int digit = 0;
        while (max != 0) { // 获取最大数的位数
            max /= 10;
            digit++;
        }
        int bucketNum = 10; // 创建10个桶
        List<List<Integer>> bucketList = new ArrayList<>();
        for (int i = 0; i < bucketNum; i++) { // 初始化每个桶
            bucketList.add(new LinkedList<>());
        }
        for (int i = 0; i < digit; i++) { // 按最低位优先依次对各关键字进行分配和收集
            for (int j = 0; j < len; j++) { // 第i趟分配
                int radix = (int) (nums[j] / Math.pow(10, i)) % 10; // 获取当前数字第i位的数
                bucketList.get(radix).add(nums[j]); // 放进对应的桶里
            }
            int k = 0;
            for (int j = bucketNum - 1; j >= 0; j--) { // 第i趟收集，按第i位从大到小的顺序将num排序
                List<Integer> bucket = bucketList.get(j);
                for (Integer num : bucket) {
                    nums[k++] = num;
                }
                bucket.clear(); // 将每个桶都清空，供下一次分配和收集使用
            }
        }
    }

    /**
     * 法十四_2（基数排序 - 递减）
     * 1. 思想
     * 按位数从低到高分配到桶中，有多少位分配多少次，分配完成后，从低位到高位依次取出
     * 2. 复杂度
     * （1）平均时间复杂度：O(n*k)
     * （2）最差时间复杂度：O(n*k)
     * （3）空间复杂度：O(n+k)
     * （4）稳定性：稳定
     * k：代表数值中的"数位"个数
     * 3. 优缺点
     * （1）优点：在数字位数相差不大的情况下具有较高效率，如[345, 652, 984, 439]，都是三位数，需要分配+收集三次
     * （2）缺点：在数字位数差距非常大时，效率低下，如[1，999999999999999]，需要分配+收集m次，m为较大数字的位数
     *
     * @param nums
     * @param k
     * @return
     */
    public int findKthLargest_14_2(int[] nums, int k) {
        radixSort_2(nums);
        return nums[k - 1];
    }
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

本地测试

        /**
         * 215. 数组中的第K个最大元素
         */
        lay.showTitle(215);
        Solution215 sol215 = new Solution215();
        int k215 = 2;
        int[] nums215_1 = new int[]{3, 2, 1, 5, 6, 4};
        System.out.println(k215 + " " + Arrays.toString(nums215_1));
        System.out.println(sol215.findKthLargest(nums215_1, k215) + " " + Arrays.toString(nums215_1));
        int[] nums215_2 = new int[]{3, 2, 1, 5, 6, 4};
        System.out.println(sol215.findKthLargest_2(nums215_2, k215) + " " + Arrays.toString(nums215_2));
        int[] nums215_3 = new int[]{3, 2, 1, 5, 6, 4};
        System.out.println(sol215.findKthLargest_3(nums215_3, k215) + " " + Arrays.toString(nums215_3));
        int[] nums215_4 = new int[]{3, 2, 1, 5, 6, 4};
        System.out.println(sol215.findKthLargest_4(nums215_4, k215) + " " + Arrays.toString(nums215_4));
        int[] nums215_5_1 = new int[]{3, 2, 1, 5, 6, 4};
        System.out.println(sol215.findKthLargest_5_1(nums215_5_1, k215) + " " + Arrays.toString(nums215_5_1));
        int[] nums215_5_2 = new int[]{3, 2, 1, 5, 6, 4};
        System.out.println(sol215.findKthLargest_5_2(nums215_5_2, k215) + " " + Arrays.toString(nums215_5_2));
        int[] nums215_6_1 = new int[]{3, 2, 1, 5, 6, 4};
        System.out.println(sol215.findKthLargest_6_1(nums215_6_1, k215) + " " + Arrays.toString(nums215_6_1));
        int[] nums215_6_2 = new int[]{3, 2, 1, 5, 6, 4};
        System.out.println(sol215.findKthLargest_6_2(nums215_6_2, k215) + " " + Arrays.toString(nums215_6_2));
        int[] nums215_7_1 = new int[]{3, 2, 1, 5, 6, 4};
        System.out.println(sol215.findKthLargest_7_1(nums215_7_1, k215) + " " + Arrays.toString(nums215_7_1));
        int[] nums215_7_2 = new int[]{3, 2, 1, 5, 6, 4};
        System.out.println(sol215.findKthLargest_7_2(nums215_7_2, k215) + " " + Arrays.toString(nums215_7_2));
        int[] nums215_8_1 = new int[]{3, 2, 1, 5, 6, 4};
        System.out.println(sol215.findKthLargest_8_1(nums215_8_1, k215) + " " + Arrays.toString(nums215_8_1));
        int[] nums215_8_2 = new int[]{3, 2, 1, 5, 6, 4};
        System.out.println(sol215.findKthLargest_8_2(nums215_8_2, k215) + " " + Arrays.toString(nums215_8_2));
        int[] nums215_9_1 = new int[]{3, 2, 1, 5, 6, 4};
        System.out.println(sol215.findKthLargest_9_1(nums215_9_1, k215) + " " + Arrays.toString(nums215_9_1));
        int[] nums215_9_2 = new int[]{3, 2, 1, 5, 6, 4};
        System.out.println(sol215.findKthLargest_9_2(nums215_9_2, k215) + " " + Arrays.toString(nums215_9_2));
        int[] nums215_10_1 = new int[]{3, 2, 1, 5, 6, 4};
        System.out.println(sol215.findKthLargest_10_1(nums215_10_1, k215) + " " + Arrays.toString(nums215_10_1));
        int[] nums215_10_2 = new int[]{3, 2, 1, 5, 6, 4};
        System.out.println(sol215.findKthLargest_10_2(nums215_10_2, k215) + " " + Arrays.toString(nums215_10_2));
        int[] nums215_11_1 = new int[]{3, 2, 1, 5, 6, 4};
        System.out.println(sol215.findKthLargest_11_1(nums215_11_1, k215) + " " + Arrays.toString(nums215_11_1));
        int[] nums215_11_2 = new int[]{3, 2, 1, 5, 6, 4};
        System.out.println(sol215.findKthLargest_11_2(nums215_11_2, k215) + " " + Arrays.toString(nums215_11_2));
        int[] nums215_12_1 = new int[]{3, 2, 1, 5, 6, 4};
        System.out.println(sol215.findKthLargest_12_1(nums215_12_1, k215) + " " + Arrays.toString(nums215_12_1));
        int[] nums215_12_2 = new int[]{3, 2, 1, 5, 6, 4};
        System.out.println(sol215.findKthLargest_12_2(nums215_12_2, k215) + " " + Arrays.toString(nums215_12_2));
        int[] nums215_13_1 = new int[]{3, 2, 1, 5, 6, 4};
        System.out.println(sol215.findKthLargest_13_1(nums215_13_1, k215) + " " + Arrays.toString(nums215_13_1));
        int[] nums215_13_2 = new int[]{3, 2, 1, 5, 6, 4};
        System.out.println(sol215.findKthLargest_13_2(nums215_13_2, k215) + " " + Arrays.toString(nums215_13_2));
        int[] nums215_14_1 = new int[]{3, 2, 1, 5, 6, 4};
        System.out.println(sol215.findKthLargest_14_1(nums215_14_1, k215) + " " + Arrays.toString(nums215_14_1));
        int[] nums215_14_2 = new int[]{3, 2, 1, 5, 6, 4};
        System.out.println(sol215.findKthLargest_14_2(nums215_14_2, k215) + " " + Arrays.toString(nums215_14_2));
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

相关阅读:
Kafka消息堆积
 学编程，为什么优先推荐学Python？
UE4(Unreal Engine4)虚幻引擎视口布局
 【数据结构】建立二叉树以及哈夫曼树及哈夫曼编码
 基于Java公益志愿捐赠管理系统设计与实现（源码+LW+调试+开题报告）
.NET周报【4月第4期 2023-04-23】
19-k8s的附加组件-coreDNS组件
 STM32基于HAL库的串口接受中断和空闲中断
 x264的参考帧管理机制
 理解系统内核linux phy驱动
原文地址：https://blog.csdn.net/qq_41829337/article/details/127127135

LeetCode-215. 数组中的第K个最大元素-Java-medium

目录

法一（随机选择算法 - 找第k个最大的数）

法二（随机选择算法 - 找第k大的数）

法三（优先级队列）

法四（计数排序）

法五_1（冒泡排序 - 递增）

法五_2（冒泡排序 - 递减）

法六_1（选择排序 - 递增）

法六_2（选择排序 - 递减）

法七_1（插入排序 - 递增）

法七_2（插入排序 - 递减）

法八_1（快速排序 - 递增）

法八_2（快速排序 - 递减）

法九_1（堆排序 - 最大堆）

法九_2（堆排序 - 最小堆）

法十_1（归并排序 - 递增）

法十_2（归并排序 - 递减）

法十一_1（希尔排序 - 递增）

法十一_2（希尔排序 - 递减）

法十二_1（计数排序 - 递增）

法十二_2（计数排序 - 递减）

法十三_1（桶排序 - 递增）

法十三_2（桶排序 - 递减）

法十四_1（基数排序 - 递增）

法十四_2（基数排序 - 递减）

本地测试