网站开发分几个模块,建立企业网站的好处,新媒体平台,免费微信小程序制作平台?1.leetcode原题链接#xff1a;. - 力扣#xff08;LeetCode#xff09;
2.题目描述
给定整数数组 nums 和整数 k#xff0c;请返回数组中第 k 个最大的元素。
请注意#xff0c;你需要找的是数组排序后的第 k 个最大的元素#xff0c;而不是第 k 个不同的元素。
你必…1.leetcode原题链接. - 力扣LeetCode
2.题目描述
给定整数数组 nums 和整数 k请返回数组中第 k 个最大的元素。
请注意你需要找的是数组排序后的第 k 个最大的元素而不是第 k 个不同的元素。
你必须设计并实现时间复杂度为 O(n) 的算法解决此问题。 示例 1:
输入: [3,2,1,5,6,4], k 2
输出: 5示例 2:
输入: [3,2,3,1,2,4,5,5,6], k 4
输出: 4 3.实现方法
方法一基于快排 在分区的过程当中我们会对子数组进行划分如果需要的下标正好就是划分得到的位置q[0]和q[1]之间 就直接返回 如果 q 比目标下标小就递归右子区间否则递归左子区间。这样就可以把原来递归两个区间变成只递归一个区间。
快速排序排序算法-快速排序-CSDN博客
class Solution {public int findKthLargest(int[] nums, int k) {if( nums.length 2){return nums[0];}return quickSort(nums,0,nums.length-1,nums.length-k);}public int quickSort(int[] arr,int l,int r,int index){if(lr){return arr[l];}swap(arr,l(int)(Math.random() * (r-l1)),r);int[] ppartition(arr,l,r);if(p[0]index indexp[1]){return arr[index];}else{return p[0]index ? quickSort(arr,p[1]1,r,index): quickSort(arr,l,p[0]-1,index);}}public int[] partition(int[] arr, int l,int r){int small l-1;int big r;while(lbig){if(arr[l]arr[r]){swap(arr,small,l);}else if(arr[l]arr[r]){swap(arr,--big,l);}else{l;}}swap(arr,big,r);return new int[]{small1,big};}public void swap(int[] arr,int a,int b){int temparr[a];arr[a]arr[b];arr[b]temp;}} 方法二基于堆排序 构建一个大顶堆做 k−1 次删除操作后堆顶元素就是要找的答案。
堆排序排序算法-堆排序-CSDN博客
class Solution {public int findKthLargest(int[] nums, int k) {if( nums.length 2){return nums[0];}int heapSizenums.length;for(int i0;iheapSize;i){heapInsert(nums,i);}while(heapSize nums.length-k1){swap(nums,0,--heapSize);heapify(nums,0,heapSize);}return nums[0];}public void heapInsert(int[] arr,int i){while(arr[i]arr[(i-1)/2]){swap(arr,i,(i-1)/2);i(i-1)/2;}}public void heapify(int[] arr, int index, int heapSize){//左孩子int left 2*index1;//当有孩子的情况下(没有左孩子一定就没有右孩子)while(left heapSize){//left1 有右孩子的情况 比较左右孩子哪个最大int largest left1 heapSize arr[left1] arr[left] ? left1 :left;//判断当前节点和子节点的数谁大largest arr[largest] arr[index] ? largest :index;//如果最大数已经是当前数了结束否则与子节点交换if(largest index){break;}swap(arr,largest,index);index largest;left 2*index 1;}}public void swap(int[] arr,int a,int b){int temparr[a];arr[a]arr[b];arr[b]temp;}}
