长沙公司网站,资源库网站开发,yw1139com最新跳转接口p,网页美工设计报价单题目链接#xff1a;力扣 解题思路#xff1a;
方法一#xff1a;基于快速排序
因为题目中只需要找到第k大的元素#xff0c;而快速排序中#xff0c;每一趟排序都可以确定一个最终元素的位置。
当使用快速排序对数组进行降序排序时#xff0c;那么如果有一趟排序过程…题目链接力扣 解题思路
方法一基于快速排序
因为题目中只需要找到第k大的元素而快速排序中每一趟排序都可以确定一个最终元素的位置。
当使用快速排序对数组进行降序排序时那么如果有一趟排序过程中确定元素的最终位置为k-1(索引从0开始)那么该元素就是第k大的元素。
具体思想下
利用快排对数组num[left...right]进行降序排序在一趟排序过程中可以确定一个元素的最终位置p将数组划分为三部分num[left...p-1]nums[p]nums[p1right]并且满足 num[left...p-1] nums[p]num[p1right] nums[p]即p位置以前的元素是数组中比p位置元素大的元素此时p位置以前的元素不一定有序但是肯定都大于等于p位置的元素而num[p]是第p1大的元素因为需要找到的是第k大的元素 如果k p那么第k大的元素肯定在num[left...p-1]内这个时候只需要对右半部分区间进行快排如果k p那么第k大的元素肯定在nums[p1right]区间内这个时候只需要对左半部分区间进行快排如果 p k-1那么nums[p]就是第k大的元素注意这种方式并不要求最终数组中的元素有序每次只会对左半部分或者右半部分进行快排减少了一般的快排调用
AC代码
class Solution {public static int findKthLargest(int[] nums, int k) {return quickSortFindK(nums, 0, nums.length - 1, k);}public static int quickSortFindK(int[] nums, int left, int right, int k) {//选取枢轴元素int pivot nums[left];int low left;int high right;while (low high) {while (low high nums[high] pivot)high--;nums[low] nums[high];while (low high nums[low] pivot)low;nums[high] nums[low];}//low或者right就是这趟排序中枢轴元素的最终位置nums[low] pivot;if (low k - 1) {return pivot;} else if (low k - 1) {return quickSortFindK(nums, left, low - 1, k);} else {return quickSortFindK(nums, low 1, right, k);}}
} 快速排序的最好时间复杂度是O(nlogn)最坏时间复杂度为O(n^2)平均时间复杂度为O(nlogn)
快速排序在元素有序的情况下效率是最低。
不过可以通过在某些情况下快速排序可以达到期望为线性的时间复杂度即O(n)也就是在每次排序前随机的交换两个元素个人理解可能是为了让元素变乱不那么有序越乱越快算法导论中在9.2 期望为线性的选择算法进行了证明还没有学习先在此记录下它的时间代价的期望是 O(n)
具体代码实现就是在排序前加上下面的代码
//随机生成一个位置该位置的范围为[left,right]
//然后将该位置的元素与最后一个元素进行交换让数组变得不那么有序
//放置出现有序的情况下快排的时间复杂度退化为o(n^2)
int randomIndex random.nextInt(right - left 1) left;
int tem nums[randomIndex];
nums[randomIndex] nums[right];
nums[right] tem;
AC代码
class Solution {static Random random new Random();public static int findKthLargest(int[] nums, int k) {return quickSortFindK(nums, 0, nums.length - 1, k);}public static int quickSortFindK(int[] nums, int left, int right, int k) {int randomIndex random.nextInt(right - left 1) left;int tem nums[randomIndex];nums[randomIndex] nums[right];nums[right] tem;int pivot nums[left];int low left;int high right;while (low high) {while (low high nums[high] pivot)high--;nums[low] nums[high];while (low high nums[low] pivot)low;nums[high] nums[low];}nums[low] pivot;if (low k - 1) {return pivot;} else if (low k - 1) {return quickSortFindK(nums, left, low - 1, k);} else {return quickSortFindK(nums, low 1, right, k);}}
} 时间上确实有了一些提升
解法二堆排序。
建立小根堆最后让小根堆里的元素个数保持在k个那么此时栈顶的元素就是k个元素中最小的,即第k大的元素
可以通过优先级队列来模拟小根堆
AC代码
class Solution {public int findKthLargest(int[] nums, int k) {PriorityQueueInteger queue new PriorityQueue();for (int num : nums) {//已经有k个元素了当前元素比堆顶元素还小不可能是第k大的元素跳过if (queue.size()kqueue.peek()num){continue;}queue.offer(num);}while (queue.size()k){queue.poll();}return queue.peek();}
}
