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

数组中的第K个最大元素题目链接https://leetcode.cn/problems/kth-largest-element-in-an-array/description/?envTypestudy-plan-v2envIdtop-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 r1; 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, j1, 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]范围内的下标假设为indexindex位置对应的元素假设为x我们采用双指针将[l,r]范围内比x大的元素都移动至x的右边比x小的元素都移动至x的左边这样我们就可以确定出x在排序后的下标我们可以直接根据下标判断出x是否为我们的目标元素若是直接返回若不是如果x排序后的下标比目标下标大我们就继续递归查找所有比x小的元素如果x排序后的下标比目标下标小那么我们就继续递归查找所有比x大的元素。重复以上操作直到查找到目标位置的元素。​ 2、方法二的解题思路构建大根堆移除k-1次大根堆的堆顶后的大根堆堆顶就是第k大的元素。总结本题的关键在于排序算法可以采用快排和堆排。快排可以确定某一个元素的位置我们不需要完全做完对数组的排序只需找到位置为n-k的元素即可所以最终采用的方法为快速选择算法。方法二的思路简单但是需要自己实现大根堆的构建和删除操作。对于构建大根堆注意不能只将元素上浮因为元素上浮之后子树不一定满足大根堆。所以我们需要采用元素下沉的方式即从第一个不是叶子节点的根节点开始对每个根节点都做下沉操作最终下沉到不能下沉为止这样我们就构建出了大根堆。对于大根堆的删除操作我们直接将最后一个叶子节点变为堆顶然后对其进行下沉操作直到不能下沉为止这样我们就完成了删除操作后大根堆的维护。