074数组中的第K个最大元素

数组中的第K个最大元素

题目链接：https://leetcode.cn/problems/kth-largest-element-in-an-array/description/?envType=study-plan-v2&envId=top-100-liked

我的解答：

无

分析：自己未能想出时间复杂度为O(n)的解法。

看了官方题解后的解答：

//方法一：基于快速排序的选择方法 //时间复杂度：O(n) //空间复杂度：O(logn) public int findKthLargest(int[] nums, int k) { int n = nums.length; return quikSelect(nums, 0, n-1, n-k); } public int quikSelect(int[] nums, int l, int r, int targetIndex){ if(l == r){ return nums[l]; } int x = nums[l]; int i = l-1, j = r+1; while(i < j){ do i++; while(nums[i] < x); do j--; while(nums[j] > x); if(i < j){ int temp = nums[i]; nums[i] = nums[j]; nums[j] = temp; } } if(targetIndex <= j){ return quikSelect(nums, l, j, targetIndex); } else{ return quikSelect(nums, j+1, r, targetIndex); } } //方法二：基于堆排序的选择方法（大根堆） //时间复杂度：O(nlogn) //空间复杂度：O(logn) public int findKthLargest(int[] nums, int k) { int heapSize = nums.length; buildMaxHeap(nums, heapSize);//构建大根堆 while(--k > 0){ swap(nums, 0, heapSize-1); heapSize--; maxHeapify(nums, 0, heapSize); } return nums[0]; } public void buildMaxHeap(int[] heap, int heapSize){ //从第一个不是叶子节点的节点开始，对每个根节点做下沉操作 //第一个不是叶子节点的下标为heapSize/2-1 for(int i = heapSize/2-1; i >= 0; i--){ maxHeapify(heap, i, heapSize);//对当前节点做下沉操作 } } public void maxHeapify(int[] heap, int cur, int heapSize){ int l = cur * 2 + 1, r = cur * 2 + 2;//计算出当前节点的左、右孩子下标 //找出cur、l、r中对应值最大的 int large = cur; if(l < heapSize && heap[l] > heap[large]){ large = l; } if(r < heapSize && heap[r] > heap[large]){ large = r; } //若cur、l、r中对应值最大的不是cur，则对交换cur和large，然后继续对子树做下沉操作。 if(large != cur){ swap(heap, cur, large); maxHeapify(heap, large, heapSize); } } public void swap(int[] heap, int x, int y){ int temp = heap[x]; heap[x] = heap[y]; heap[y] = temp; }

分析：

​ 1、方法一的解题思路：根据题意，我们很容易想到将数组排序后返回位置为n-k的元素。所以我们就容易想到快排，但是一般的快排时间复杂度为nlogn，显然不满足题目要求的O(n)的时间复杂度，因此我们进一步想到了随机快速排序。根据快排的性质，我们随机选择一个[l,r]范围内的下标，假设为index，index位置对应的元素假设为x，我们采用双指针将[l,r]范围内比x大的元素都移动至x的右边，比x小的元素都移动至x的左边，这样我们就可以确定出x在排序后的下标，我们可以直接根据下标判断出x是否为我们的目标元素，若是，直接返回；若不是，如果x排序后的下标比目标下标大，我们就继续递归查找所有比x小的元素；如果x排序后的下标比目标下标小，那么我们就继续递归查找所有比x大的元素。重复以上操作直到查找到目标位置的元素。

​ 2、方法二的解题思路：构建大根堆，移除k-1次大根堆的堆顶后的大根堆堆顶就是第k大的元素。

总结

• 本题的关键在于排序算法，可以采用快排和堆排。
• 快排可以确定某一个元素的位置，我们不需要完全做完对数组的排序，只需找到位置为n-k的元素即可，所以最终采用的方法为快速选择算法。
• 方法二的思路简单，但是需要自己实现大根堆的构建和删除操作。对于构建大根堆，注意，不能只将元素上浮，因为元素上浮之后，子树不一定满足大根堆。所以我们需要采用元素下沉的方式，即从第一个不是叶子节点的根节点开始，对每个根节点都做下沉操作，最终下沉到不能下沉为止，这样我们就构建出了大根堆。对于大根堆的删除操作，我们直接将最后一个叶子节点变为堆顶，然后对其进行下沉操作直到不能下沉为止，这样我们就完成了删除操作后大根堆的维护。