深圳网站设计公司yx成都柚米科技15,网站建设为中心,双语网站管理系统,网站建设答辩ppt大家好我是苏麟 , 今天带来一道应用快排的题 .
数组中的第K个最大元素
描述 :
给定整数数组 nums 和整数 k#xff0c;请返回数组中第 k 个最大的元素。
请注意#xff0c;你需要找的是数组排序后的第 k 个最大的元素#xff0c;而不是第 k 个不同的元素。
题目 :
Le…大家好我是苏麟 , 今天带来一道应用快排的题 .
数组中的第K个最大元素
描述 :
给定整数数组 nums 和整数 k请返回数组中第 k 个最大的元素。
请注意你需要找的是数组排序后的第 k 个最大的元素而不是第 k 个不同的元素。
题目 :
LeetCode 215.数组中的第K个最大元素 :
215. 数组中的第K个最大元素 分析 :
这道题基于快排完成 , 快排教程 : 算法通关村第十关-青铜挑战快速排序-CSDN博客 这道题还有一个地方就是K这 , 举例 :数组 num [1,2,3,4,5,6,7,8,9] 一个升序的数组 找第1个大的值就是 9 ,就找 9 的下标 也就是 num.length - k , 懂了这里我们看一下下面的代码 : if(i k){return sort(nums,i 1,right,k);}else{return sort(nums,left,i - 1,k);} i 这里就是中间值 , 在 i 左边的都比 num[i] 小 , 在 i 右边的都比num[i] 大 , 所以要找第一大的就在 i 右边找就好了 , 因为左边都是比num[i] 小的 ...... 这里也懂了的话就题就完事了 , 这题还是有些难度的 .
用双边快排
解析 :
class Solution {public int findKthLargest(int[] nums,int k) {int length nums.length;return sort(nums,0,length - 1,length - k);}public int sort(int[] nums,int left,int right,int k){int i qicke(nums,left,right);if(i k){return nums[k];}if(i k){return sort(nums,i 1 , right ,k);}else{return sort(nums,left,i - 1,k);}// sort(nums,left,i - 1,k);// sort(nums,i 1,right,k);}public int qicke(int[] nums,int left,int right){int i left;int j right;int p nums[left];while(i j){while(i j nums[j] p){j--;}while(i j nums[i] p){i;}swap(nums,i,j);}swap(nums,i,left);return i; }public void swap(int[]nums,int i,int j){int temp nums[i];nums[i]nums[j];nums[j]temp;}
}
分析 :
用单边快排
解析 :
class Solution {public int findKthLargest(int[] nums, int k) {int n nums.length;return sort(nums,0,n - 1,n - k);}public int sort(int[] nums,int left,int right,int k){int i qicke(nums,left,right,k);if(i k){return nums[k];}if(i k){return sort(nums,i 1,right,k);}else{return sort(nums,left,i - 1,k);}}public int qicke(int[] nums,int left,int right,int k){int i left;int j left;int p nums[right];while(j right){if(nums[j] p){if(i ! j){swap(nums,i,j);}i;}j;}swap(nums,i,right);return i; }public void swap(int[]nums,int i,int j){int temp nums[i];nums[i]nums[j];nums[j]temp;}
} 这题需要大家好好理解 , 并独立写出来 . 这道题 , 我也是弄了很久 ,下面是我的提交记录(太惨了) , 希望大家做的又快又对 ...... 这期就到这里 , 下期见!
