江苏天宇建设集团有限公司网站,小程序开发工具编辑器,这么攻击网站,代码网页制作#x1f34e;道阻且长#xff0c;行则将至。#x1f353; #x1f33b;算法#xff0c;不如说它是一种思考方式#x1f340;算法专栏#xff1a; #x1f449;#x1f3fb;123 一、#x1f331;215. 数组中的第K个最大元素
题目描述#xff1a;给定整数数组nums和整… 道阻且长行则将至。 算法不如说它是一种思考方式 算法专栏 123 一、215. 数组中的第K个最大元素
题目描述给定整数数组nums和整数** k**请返回数组中第 k 个最大的元素。 请注意你需要找的是数组排序后的第 k 个最大的元素而不是第 k 个不同的元素。你必须设计并实现时间复杂度为 O(n) 的算法解决此问题。来源力扣LeetCode难度中等提示 1 k nums.length 105 -104 nums[i] 104
本题也出现在剑指offer II 076. 数组中的第 k 大的数字不过测试案例更友好。
解题
对于本题最常规的解法就是先大到小排序然后返回第k个元素即可时间复杂度越低越好。 对于友好的测试案例也可以使用大小为k的数组进行一次目标变量存储前k大的数。
1.排序法
1.1冒泡排序
最简单的是冒泡排序方法非常简单使用两层循环进行逐一遍历时间复杂度为O(n2)。参考冒泡排序☝
1.2快速排序
在这个题目要求的O(n)时间复杂度冒泡法是无法通过的因此考虑快一点的排序算法快速排序。大到小为例 快速排序最直观的理解就是每次选择的key元素或者基准经过一趟排序后放在了最终所在的位置也就是左边大于key元素右边小于key元素。于是数组被区分为了两个子区间再继续在两个子区间用同样的方法。这也被称之为分治策略就是把大的问题变成一个个小的问题最后组合起来。 例如数组{4,2,3,5,6,1}对于其中的一次排序 我们选取第一个元素为了key下一个为p最后一个为q。step1.q向左遍历遇到大于key的元素的位置停下来step2.p向右遍历遇到小于key的停下来然后交换pq的元素值。一直重复直到pq相遇与key交换结束 这是其中一种方法还有挖坑填数、快慢指针
挖坑填数 挖坑填数就是在上一个方法的基础上来的选择的key元素先挖出来q指针往左走发现大于key时就把这个元素挖出来填到上一个坑里于是新坑出现了然后p向右走遇到小于key的也挖出来填到上一个坑里一直这样的过程直到pq相遇将key最后填入这个坑里。指针是一直向坑遍历 快慢指针fast、slow 前面两种方法的指针都是从两端向中间该方法的指针都是从左至右都是从key的下一位往右走快指针每走一步都会判断其指向的元素是否大等于key若小于则交换两个指针的元素并且让慢指针移动1位直到fast遍历完全slow退回一步预期的向前了一步交换slow和key。 快速排序和冒泡排序解题code:
class Solution076 {public static int findKthLargest(int[] nums, int k) {//排序// bobosort(nums);//快速排序fastsort(nums);return nums[k-1];}private static void fastsort(int[] nums) {int left0,right nums.length-1;myquicksort(nums,left,right);}private static void myquicksort(int[] nums, int left, int right) {if(leftright)return;int keypartsort(nums,left,right);myquicksort(nums,left,key-1);myquicksort(nums, key1, right);}private static int partsort(int[] nums, int left, int right) {int keyleft;while(leftright){while(leftrightnums[right]nums[key])right--;while(leftrightnums[left]nums[key])left;myswap(nums,left,right);}myswap(nums,key,left);return left;}private static void myswap(int[] nums, int left, int right) {int tem;temnums[left];nums[left]nums[right];nums[right]tem;}public static int[] bobosort(int[] nums){int tem;for (int i 0; i nums.length-1; i) {for (int j i1; j nums.length; j) {if(nums[i]nums[j]){temnums[i];nums[i]nums[j];nums[j]tem;}}}return nums;}}1.3快速排序思想简化本题
在前面就发现本题其实找到某个位置之后的一些步骤不需要进行了例如我们找第8个大的数在第1次找到第六个元素那么第8大的元素必然是在后面部分前面部分数组就可以不管了当刚好找到第8个时直接返回就是我们的结果。这样可以大大减少搜索时间。
code
class Solution {publicint findKthLargest(int[] nums, int k) {int key0;int left0;int right nums.length - 1;quicksort1(nums,key,left,right,k-1);return nums[k-1];}private static void quicksort1(int[] nums, int key, int left, int right, int k) {if(leftright)return;key partsort( nums, key, left, right);if(keyk){quicksort1(nums,key1,key1,right,k);}else if(keyk){return;}else{quicksort1(nums,left,left,key-1,k);}}private static int partsort(int[] nums, int key, int left, int right) {int slowkey1;int fastkey1;int temp;while (fastright){if(nums[fast]nums[key]){tempnums[slow];nums[slow]nums[fast];nums[fast]temp;slow;}fast;}slow--;tempnums[key];nums[key]nums[slow];nums[slow]temp;return slow;}
}2.大小为k数组
就是说使用一个大小为k的数组来存储遍历找到前k个最大的数只需要遍历一遍数组但是数组k的处理还是需要耗费时间的。
code
class Solution076 {public static int findKthLargest(int[] nums, int k) {int[] numk new int[k];int j0;for (int i 0; i nums.length; i) {if(ik){numk[i]nums[i];}else{jfindKless(numk);if(numk[j]nums[i])numk[j]nums[i];}}jfindKless(numk);return numk[j];}public static int findKless(int[] nums){int k0;for (int i 1; i nums.length; i) {if(nums[k]nums[i])ki;}return k;}
}该方法只能通过剑指offer的案例 t215 剑指offer Bug本是code常态通过才是稀缺的意外返回第一页☝ ☕物有本末事有终始知所先后。 ☝☝☝☝☝我的CSDN☝☝☝☝☝☝
