[Leedcode][第215题][JAVA][数组中的第K个最大元素][快排][优先队列]

清疚 2023-02-21 06:24 3阅读 0赞

#### 【问题描述】\[中等\] ####

在未排序的数组中找到第 k 个最大的元素。请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。
    
    示例 1:
    
    输入: [3,2,1,5,6,4] 和 k = 2
    输出: 5
    示例 2:
    
    输入: [3,2,3,1,2,4,5,5,6] 和 k = 4
    输出: 4
    说明:
    
    你可以假设 k 总是有效的，且 1 ≤ k ≤ 数组的长度。

#### 【解答思路】 ####

###### 1. 暴力解法（快排） ######

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70]  
**时间复杂度：O(NlogN) 空间复杂度：O(1)**

import java.util.Arrays;
    
    public class Solution { 
    
        public int findKthLargest(int[] nums, int k) { 
            int len = nums.length;
            Arrays.sort(nums);
            return nums[len - k];
        }
    }

###### 2. 借助 partition 操作定位到最终排定以后索引为 len - k 的那个元素（特别注意：随机化切分元素） ######

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70 1]  
**时间复杂度：O(N) 空间复杂度：O(1)**  
![在这里插入图片描述][2020062910545745.png]

public class Solution { 
    
        public int findKthLargest(int[] nums, int k) { 
            int len = nums.length;
            int left = 0;
            int right = len - 1;
    
            // 转换一下，第 k 大元素的索引是 len - k
            int target = len - k;
    
            while (true) { 
                int index = partition(nums, left, right);
                if (index == target) { 
                    return nums[index];
                } else if (index < target) { 
                    left = index + 1;
                } else { 
                    right = index - 1;
                }
            }
        }
    
        /** * 在数组 nums 的子区间 [left, right] 执行 partition 操作，返回 nums[left] 排序以后应该在的位置 * 在遍历过程中保持循环不变量的语义 * 1、[left + 1, j] < nums[left] * 2、(j, i] >= nums[left] * * @param nums * @param left * @param right * @return */
        public int partition(int[] nums, int left, int right) { 
            int pivot = nums[left];
            int j = left;
            for (int i = left + 1; i <= right; i++) { 
                if (nums[i] < pivot) { 
                    // 小于 pivot 的元素都被交换到前面
                    j++;
                    swap(nums, j, i);
                }
            }
            // 在之前遍历的过程中，满足 [left + 1, j] < pivot，并且 (j, i] >= pivot
            swap(nums, j, left);
            // 交换以后 [left, j - 1] < pivot, nums[j] = pivot, [j + 1, right] >= pivot
            return j;
        }
    
        private void swap(int[] nums, int index1, int index2) { 
            int temp = nums[index1];
            nums[index1] = nums[index2];
            nums[index2] = temp;
        }
    }

![在这里插入图片描述][20200629105521802.png]

import java.util.Random;
    
    public class Solution { 
    
        private static Random random = new Random(System.currentTimeMillis());
    
        public int findKthLargest(int[] nums, int k) { 
            int len = nums.length;
            int target = len - k;
            int left = 0;
            int right = len - 1;
            while (true) { 
                int index = partition(nums, left, right);
                if (index < target) { 
                    left = index + 1;
                } else if (index > target) { 
                    right = index - 1;
                } else { 
                    return nums[index];
                }
            }
        }
    
        // 在区间 [left, right] 这个区间执行 partition 操作
    
        private int partition(int[] nums, int left, int right) { 
            // 在区间随机选择一个元素作为标定点
            if (right > left) { 
                int randomIndex = left + 1 + random.nextInt(right - left);
                swap(nums, left, randomIndex);
            }
    
            int pivot = nums[left];
            int j = left;
            for (int i = left + 1; i <= right; i++) { 
                if (nums[i] < pivot) { 
                    j++;
                    swap(nums, j, i);
                }
            }
            swap(nums, left, j);
            return j;
        }
    
        private void swap(int[] nums, int index1, int index2) { 
            int temp = nums[index1];
            nums[index1] = nums[index2];
            nums[index2] = temp;
        }
    }

![在这里插入图片描述][20200629110340672.png]

import java.util.Random;
    
    public class Solution { 
    
        private static Random random = new Random(System.currentTimeMillis());
    
        public int findKthLargest(int[] nums, int k) { 
            int len = nums.length;
            int left = 0;
            int right = len - 1;
    
            // 转换一下，第 k 大元素的索引是 len - k
            int target = len - k;
    
            while (true) { 
                int index = partition(nums, left, right);
                if (index == target) { 
                    return nums[index];
                } else if (index < target) { 
                    left = index + 1;
                } else { 
                    right = index - 1;
                }
            }
        }
    
        public int partition(int[] nums, int left, int right) { 
            // 在区间随机选择一个元素作为标定点
            if (right > left) { 
                int randomIndex = left + 1 + random.nextInt(right - left);
                swap(nums, left, randomIndex);
            }
    
            int pivot = nums[left];
    
            // 将等于 pivot 的元素分散到两边
            // [left, lt) <= pivot
            // (rt, right] >= pivot
    
            int lt = left + 1;
            int rt = right;
    
            while (true) { 
                while (lt <= rt && nums[lt] < pivot) { 
                    lt++;
                }
                while (lt <= rt && nums[rt] > pivot) { 
                    rt--;
                }
    
                if (lt > rt) { 
                    break;
                }
                swap(nums, lt, rt);
                lt++;
                rt--;
            }
    
            swap(nums, left, rt);
            return rt;
        }
    
        private void swap(int[] nums, int index1, int index2) { 
            int temp = nums[index1];
            nums[index1] = nums[index2];
            nums[index2] = temp;
        }
    }

###### 3. 优先队列 ######

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70 2]

import java.util.PriorityQueue;
    
    public class Solution { 
    
        public int findKthLargest(int[] nums, int k) { 
            int len = nums.length;
            // 使用一个含有 len 个元素的最小堆，默认是最小堆，可以不写 lambda 表达式：(a, b) -> a - b
            PriorityQueue<Integer> minHeap = new PriorityQueue<>(len, (a, b) -> a - b);
            for (int i = 0; i < len; i++) { 
                minHeap.add(nums[i]);
            }
            for (int i = 0; i < len - k; i++) { 
                minHeap.poll();
            }
            return minHeap.peek();
        }
    }

import java.util.PriorityQueue;
    
    public class Solution { 
    
        public int findKthLargest(int[] nums, int k) { 
            int len = nums.length;
            // 使用一个含有 len 个元素的最大堆，lambda 表达式应写成：(a, b) -> b - a
            PriorityQueue<Integer> maxHeap = new PriorityQueue<>(len, (a, b) -> b - a);
            for (int i = 0; i < len; i++) { 
                maxHeap.add(nums[i]);
            }
            for (int i = 0; i < k - 1; i++) { 
                maxHeap.poll();
            }
            return maxHeap.peek();
        }
    }

![在这里插入图片描述][20200629110805951.png]

import java.util.PriorityQueue;
    
    public class Solution { 
    
        public int findKthLargest(int[] nums, int k) { 
            int len = nums.length;
            // 使用一个含有 k 个元素的最小堆
            PriorityQueue<Integer> minHeap = new PriorityQueue<>(k, (a, b) -> a - b);
            for (int i = 0; i < k; i++) { 
                minHeap.add(nums[i]);
            }
            for (int i = k; i < len; i++) { 
                // 看一眼，不拿出，因为有可能没有必要替换
                Integer topEle = minHeap.peek();
                // 只要当前遍历的元素比堆顶元素大，堆顶弹出，遍历的元素进去
                if (nums[i] > topEle) { 
                    minHeap.poll();
                    minHeap.add(nums[i]);
                }
            }
            return minHeap.peek();
        }
    }

![在这里插入图片描述][20200629110835412.png]

import java.util.PriorityQueue;
    
    public class Solution { 
    
        public int findKthLargest(int[] nums, int k) { 
            int len = nums.length;
            // 最小堆
            PriorityQueue<Integer> priorityQueue = new PriorityQueue<>(k + 1, (a, b) -> (a - b));
            for (int i = 0; i < k; i++) { 
                priorityQueue.add(nums[i]);
            }
            for (int i = k; i < len; i++) { 
                priorityQueue.add(nums[i]);
                priorityQueue.poll();
            }
            return priorityQueue.peek();
        }
    }

![在这里插入图片描述][20200629111032671.png]

import java.util.PriorityQueue;
    
    public class Solution { 
    
        // 根据 k 的不同，选最大堆和最小堆，目的是让堆中的元素更小
        // 思路 1：k 要是更靠近 0 的话，此时 k 是一个较大的数，用最大堆
        // 例如在一个有 6 个元素的数组里找第 5 大的元素
        // 思路 2：k 要是更靠近 len 的话，用最小堆
    
        // 所以分界点就是 k = len - k
    
        public int findKthLargest(int[] nums, int k) { 
            int len = nums.length;
            if (k <= len - k) { 
                // System.out.println("使用最小堆");
                // 特例：k = 1，用容量为 k 的最小堆
                // 使用一个含有 k 个元素的最小堆
                PriorityQueue<Integer> minHeap = new PriorityQueue<>(k, (a, b) -> a - b);
                for (int i = 0; i < k; i++) { 
                    minHeap.add(nums[i]);
                }
                for (int i = k; i < len; i++) { 
                    // 看一眼，不拿出，因为有可能没有必要替换
                    Integer topEle = minHeap.peek();
                    // 只要当前遍历的元素比堆顶元素大，堆顶弹出，遍历的元素进去
                    if (nums[i] > topEle) { 
                        minHeap.poll();
                        minHeap.add(nums[i]);
                    }
                }
                return minHeap.peek();
    
            } else { 
                // System.out.println("使用最大堆");
                assert k > len - k;
                // 特例：k = 100，用容量为 len - k + 1 的最大堆
                int capacity = len - k + 1;
                PriorityQueue<Integer> maxHeap = new PriorityQueue<>(capacity, (a, b) -> b - a);
                for (int i = 0; i < capacity; i++) { 
                    maxHeap.add(nums[i]);
                }
                for (int i = capacity; i < len; i++) { 
                    // 看一眼，不拿出，因为有可能没有必要替换
                    Integer topEle = maxHeap.peek();
                    // 只要当前遍历的元素比堆顶元素大，堆顶弹出，遍历的元素进去
                    if (nums[i] < topEle) { 
                        maxHeap.poll();
                        maxHeap.add(nums[i]);
                    }
                }
                return maxHeap.peek();
            }
        }
    }

#### 【总结】 ####

###### 1.快排核心思想 找partition 随机化可避免极端情况 ######

###### 2.优先队列的使用 最大最小堆 ######

//大堆
    PriorityQueue<Integer> maxHeap = new PriorityQueue<>(capacity, (a, b) -> b - a);
    //小堆
     PriorityQueue<Integer> minHeap = new PriorityQueue<>(k, (a, b) -> a - b);

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70 3]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70 4]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70 5]

###### 3.assert 调试使用 程序或软件正式发布后需要关闭 ######

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70 6]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70 7]

转载链接：https://leetcode-cn.com/problems/kth-largest-element-in-an-array/solution/partitionfen-er-zhi-zhi-you-xian-dui-lie-java-dai-/

参考链接：https://blog.csdn.net/jeikerxiao/article/details/82262487  
参考链接：https://www.cnblogs.com/wei-jing/p/10806236.html

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200629103209469.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk=,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20200629103941918.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk=,size_16,color_FFFFFF,t_70
[2020062910545745.png]: https://img-blog.csdnimg.cn/2020062910545745.png
[20200629105521802.png]: https://img-blog.csdnimg.cn/20200629105521802.png
[20200629110340672.png]: https://img-blog.csdnimg.cn/20200629110340672.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70 2]: https://img-blog.csdnimg.cn/20200629110729983.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk=,size_16,color_FFFFFF,t_70
[20200629110805951.png]: https://img-blog.csdnimg.cn/20200629110805951.png
[20200629110835412.png]: https://img-blog.csdnimg.cn/20200629110835412.png
[20200629111032671.png]: https://img-blog.csdnimg.cn/20200629111032671.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70 3]: https://img-blog.csdnimg.cn/20200629112711457.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk=,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70 4]: https://img-blog.csdnimg.cn/2020062911281741.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk=,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70 5]: https://img-blog.csdnimg.cn/20200629112915469.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk=,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70 6]: https://img-blog.csdnimg.cn/20200629112148815.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk=,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70 7]: https://img-blog.csdnimg.cn/20200629112202165.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk=,size_16,color_FFFFFF,t_70