LeetCode：215. Kth Largest Element in an Array（输出第k大的数）

我不是女神ヾ 2022-04-08 11:55 139阅读 0赞

> **文章最前**： 我是Octopus，这个名字来源于我的中文名--章鱼；我热爱编程、热爱算法、热爱开源。所有源码在我的个人[github][] ；这博客是记录我学习的点点滴滴，如果您对 Python、Java、AI、算法有兴趣，可以关注我的动态，一起学习，共同进步。

**相关文章：**

1.  **[LeetCode：55. Jump Game（跳远比赛）][LeetCode_55. Jump Game]**
2.  **[Leetcode：300. Longest Increasing Subsequence（最大增长序列）][Leetcode_300. Longest Increasing Subsequence]**
3.  **[LeetCode：560. Subarray Sum Equals K（找出数组中连续子串和等于k][LeetCode_560. Subarray Sum Equals K_k]**

--------------------

**文章目录：**

题目描述：

java实现方法1：利用队列的形式

python实现方式1：

java实现方式2：

python实现方式2：

源码github地址：

--------------------

### 题目描述： ###

在未排序的数组中找到第 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 ≤ 数组的长度。

--------------------

著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

--------------------

### java实现方法1：利用队列的形式 ###

/**
         * 找出第k小的值
         *
         * @param nums 数组
         * @param k    个数
         * @return 数字
         */
        private int kthLargestElement(int[] nums, int k) {
            Queue<Integer> queue = new PriorityQueue<>();
            for (int num : nums) {
                queue.add(num);
            }
            for (int i = 0; i < k - 1; i++) {
                queue.poll();
            }
            return queue.peek();
        }

时间复杂度：O（n.k）

空间复杂度：O（k）

--------------------

### python实现方式1： ###

def kth_largest_element_num_1(self, nums: List[int], k: int) -> int:
            '''
                找出第K个大的数
            Args:
                nums: 数组
                k: k个最大数
            Returns:
                第k大那个数
            '''
            pq = PQ()
            for ele in nums:
                pq.put(ele)
                if pq.qsize() > k:
                    pq.get()
            return pq.get()

时间复杂度：O（n.logn）

空间复杂度：O（k）

--------------------

### java实现方式2： ###

/**
         * 找出第k大的值
         *
         * @param nums 数组
         * @param k    个数
         * @return 数字
         */
        private int kthLargestElement2(Integer[] nums, int k) {
            if (nums == null || nums.length < k) {
                return -1;
            }
            return quickSort(nums, 0, nums.length - 1, k);
        }
    
        /**
         * 快速排序选择元素
         *
         * @param nums 数组
         * @param l    位置l
         * @param r    位置r
         * @param k    第k大的数
         * @return 数字
         */
        private int quickSort(Integer[] nums, int l, int r, int k) {
            int index = randomPartition(nums, l, r);
            if (index == k - 1) {
                return nums[k - 1];
            } else if (index > k - 1) {
                return quickSort(nums, l, index - 1, k);
            } else {
                return quickSort(nums, index + 1, r, k);
            }
        }
    
        /**
         * 随机划分
         *
         * @param nums 数组
         * @param l    位置l
         * @param r    位置r
         * @return 选择位置
         */
        private int randomPartition(Integer[] nums, int l, int r) {
            int i = (int) Math.random() * (r - l) + l;
            swap(nums, i, r);
            return partition(nums, l, r);
        }
    
        /**
         * 划分数组，比阈值大的在左边，比阈值小的在右边
         *
         * @param nums 数组
         * @param l    位置l
         * @param r    位置r
         * @return 阈值位置
         */
        private int partition(Integer[] nums, int l, int r) {
            int pivot = nums[r];
            int rightMost = r;
            while (l <= r) {
                while (l <= r && nums[l] > pivot) {
                    l++;
                }
                while (l <= r && nums[r] <= pivot) {
                    r--;
                }
                if (l <= r) {
                    swap(nums, l, r);
                }
            }
            swap(nums, l, rightMost);
            return l;
        }
    
        /**
         * 交换数组中两个元素的位置
         *
         * @param nums 数组
         * @param l    位置l
         * @param r    位置r
         */
        private void swap(Integer[] nums, int l, int r) {
            int temp = nums[l];
            nums[l] = nums[r];
            nums[r] = temp;
        }

时间复杂度：O（n.k）

空间复杂度：O（1）

### python实现方式2： ###

def kth_largest_element_num_2(self, nums: List[int], k: int) -> int:
            '''
                找出第K个大的数
            Args:
                nums: 数组
                k: k个最大数
            Returns:
                第k大那个数
            '''
            if nums == None or len(nums) < k:
                return None
            return self.quick_sort(nums, 0, len(nums) - 1, k)
    
        def quick_sort(self, nums: List[int], l: int, r: int, k: int) -> int:
            '''
                快速排序
            Args:
                nums: 数组
                l: 位置l
                r: 位置r
                k:  第k大的数
            Returns:
                数字
            '''
            index = self.random_partition(nums, l, r)
            if index == k - 1:
                return nums[k - 1]
            elif index > k - 1:
                return self.quick_sort(nums, l, index - 1, k)
            else:
                return self.quick_sort(nums, index + 1, r, k)
    
        def random_partition(self, nums: List[int], l: int, r: int) -> int:
            '''
                随机生成数组
            Args:
                nums: 数组
                l:位置l
                r:位置r
            Returns:
                位置
            '''
            i = random.randint(l, r)
            self.swap(nums, i, r)
            return self.partition(nums, l, r)
    
        def swap(self, nums: List[int], l: int, r: int) -> None:
            """
                交换两个数的位置
            Args:
                nums: 数组
                l: 位置l
                r: 位置r
            Returns:
                None
            """
            temp = nums[l]
            nums[l] = nums[r]
            nums[r] = temp
    
        def partition(self, nums: List[int], l: int, r: int) -> int:
            '''
                分组
            Args:
                nums: 数组
                l: 位置l
                r: 位置r
            Returns:
                分组
            '''
            pivot = nums[r]
            right_most = r
            while l <= r:
                while l <= r and nums[l] > pivot:
                    l += 1
                while l <= r and nums[r] <= pivot:
                    r -= 1
                if l <= r:
                    self.swap(nums, l, r)
            self.swap(nums, l, right_most)
            return l

时间复杂度：O（n.k）

空间复杂度：O（1）

--------------------

### 源码github地址： ###

[https://github.com/zhangyu345293721/leetcode][https_github.com_zhangyu345293721_leetcode]

[github]: https://github.com/zhangyu345293721
[LeetCode_55. Jump Game]: https://blog.csdn.net/zy345293721/article/details/84991870
[Leetcode_300. Longest Increasing Subsequence]: https://blog.csdn.net/zy345293721/article/details/84984249
[LeetCode_560. Subarray Sum Equals K_k]: https://blog.csdn.net/zy345293721/article/details/84952201
[https_github.com_zhangyu345293721_leetcode]: https://github.com/zhangyu345293721/leetcode