数组中的第K个最大元素

灰太狼 2023-07-14 12:58 75阅读 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 ≤ 数组的长度。

**解题思路：**  
这个是个典型的 Top K 问题，而且题目里面没有说明数据量的大小或限定的内存，那么直接用堆排序秒了就行。  
思路是创建一个小顶堆，将所有数组中的元素加入堆中，并保持堆的大小小于等于 k。这样，堆中就保留了前 k 个最大的元素。这样，堆顶的元素就是正确答案。  
向大小为 k 的堆中添加元素的时间复杂度为 O(log k)，我们将重复该操作 N 次，故总时间复杂度为 O(N\*log k)  
贴出笔者的代码：

class Solution { 
        
        //返回第K个最大的元素
        public int findKthLargest(int[] nums, int k) { 
    
    		//创建一个堆
            int[] haep = new int[k];
            for(int i=0; i<k; i++) { 
                haep[i] = nums[i];
            }
            
            //把堆调整为小顶堆
            for(int i = haep.length / 2 - 1; i >=0; i--) { 
                adjustHeap(haep, i, k);
            }
    
    		//循环遍历，对每个元素进行调整
            for(int i=k; i<nums.length; i++) { 
                if(nums[i] > haep[0]) { 
                    haep[0] = nums[i];
                    adjustHeap(haep, 0, k);
                }
            }
    
            return haep[0];
        }
    
    	//单次调整
        public  static void adjustHeap(int arr[], int i, int lenght) { 
    
            int temp = arr[i];//先取出当前元素的值，保存在临时变量
            //开始调整
            //说明
            //1. k = i * 2 + 1 k 是 i结点的左子结点
            for(int k = i * 2 + 1; k < lenght; k = k * 2 + 1) { 
                if(k+1 < lenght && arr[k] > arr[k+1]) {  //说明左子结点的值小于右子结点的值
                    k++; // k 指向右子结点
                }
                if(arr[k] < temp) {  //如果子结点大于父结点
                    arr[i] = arr[k]; //把较大的值赋给当前结点
                    i = k; //!!! i 指向 k,继续循环比较
                } else { 
                    break;//!
                }
            }
            //当for 循环结束后，我们已经将以i 为父结点的树的最大值，放在了 最顶(局部)
            arr[i] = temp;//将temp值放到调整后的位置
        }
    }