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

朱雀 2023-02-23 08:27 88阅读 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

## 题解 ##

[方法二][Link 1]：借助 partition 操作定位到最终排定以后索引为 len - k 的那个元素

以下的描述基于 “快速排序” 算法知识的学习，如果忘记的朋友们可以翻一翻自己的《数据结构与算法》教材，复习一下，partition 过程、分治思想和 “快速排序” 算法的优化。

分析：我们在学习 “**快速排序**” 的时候，接触的第 1 个操作就是 `partition（切分）`，简单介绍如下：

partition（切分）操作，使得：

对于某个索引 `j`，`nums[j]` 已经排定，即 `nums[j]` 经过 partition（切分）操作以后会放置在它 “最终应该放置的地方”；  
`nums[left]`到 `nums[j - 1]` 中的所有元素都不大于 `nums[j]`；  
`nums[j + 1]` 到 `nums[right]`中的所有元素都不小于 `nums[j]`。

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

partition（切分）操作总能排定一个元素，还能够知道这个元素它最终所在的位置，这样每经过一次 partition（切分）操作就能缩小搜索的范围，这样的思想叫做 “减而治之”（是 “分而治之” 思想的特例）。

java代码如下：

class Solution {
        
        public int findKthLargest(int[] nums, int k) {
        
            int left = 0;
            int right = nums.length -1;
            int pivot = nums[0];
            int target = nums.length - k;
    
            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];
                }
            }
        }
    
        public int partition(int[] nums,int left,int right){
        
            if(left > right){
        
                return -1;
            }
    
            int temp = nums[left];
            int i = left;
            int j = right;
    
            while(i != j){
        
                while(nums[j] >= temp && j > i){
        
                    j --;
                }
    
                while(nums[i] <= temp && j > i){
        
                    i ++;
                }
    
                if(i < j){
        
                    int t = nums[i];
                    nums[i] = nums[j];
                    nums[j] = t;
                }
            }
    
            nums[left] = nums[i];
            nums[i] = temp;
    
            return i;
        }
    }

python代码：

class Solution:
        def findKthLargest(self, nums: List[int], k: int) -> int:
            left = 0
            right = len(nums) - 1
            pivot = nums[0]
            target = len(nums) - k
    
            while True:
                index = self.partition(nums, left, right)
    
                if index == target:
                    return nums[index]
                elif index < target:
                    left = index + 1
                elif index > target:
                    right = index - 1
        
        def partition(self, nums: List[int], left : int, right: int):
            if left > right:
                return -1
            
            tmp = nums[left]
            i = left
            j = right
            while i != j:
                while j > i and nums[j] >= tmp:
                    j = j - 1
                while j > i and nums[i] <= tmp:
                    i = i + 1
                
                if i < j:
                    nums[i], nums[j] = nums[j], nums[i]
                
            nums[left] = nums[i]
            nums[i] = tmp
            return i

[Link 1]: https://leetcode-cn.com/problems/kth-largest-element-in-an-array/solution/partitionfen-er-zhi-zhi-you-xian-dui-lie-java-dai-/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzk5OTMyNw_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200706161151958.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzk5OTMyNw==,size_16,color_FFFFFF,t_70