LeetCode：215. 数组中的第K个最大元素

🍎道阻且长，行则将至。🍓

---

🌻算法，不如说它是一种思考方式🍀

算法专栏： 👉🏻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(n²)。参考：冒泡排序☝

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 left=0,right= nums.length-1;myquicksort(nums,left,right);}private static void myquicksort(int[] nums, int left, int right) {if(left>right)return;int key=partsort(nums,left,right);myquicksort(nums,left,key-1);myquicksort(nums, key+1, right);}private static int partsort(int[] nums, int left, int right) {int key=left;while(left<right){while(left<right&&nums[right]<=nums[key])right--;while(left<right&&nums[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;tem=nums[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 = i+1; j < nums.length; j++) {if(nums[i]<nums[j]){tem=nums[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 key=0;int left=0;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(left>right)return;key = partsort( nums,  key,  left,  right);if(key<k){quicksort1(nums,key+1,key+1,right,k);}else if(key==k){return;}else{quicksort1(nums,left,left,key-1,k);}}private static int partsort(int[] nums, int key, int left, int right) {int slow=key+1;int fast=key+1;int temp;while (fast<=right){if(nums[fast]>=nums[key]){temp=nums[slow];nums[slow]=nums[fast];nums[fast]=temp;slow++;}fast++;}slow--;temp=nums[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 j=0;for (int i = 0; i < nums.length; i++) {if(i<k){numk[i]=nums[i];}else{j=findKless(numk);if(numk[j]<nums[i])numk[j]=nums[i];}}j=findKless(numk);return numk[j];}public static int findKless(int[] nums){int k=0;for (int i = 1; i < nums.length; i++) {if(nums[k]>nums[i])k=i;}return k;}
}

该方法只能通过剑指offer的案例：
t215

剑指offer：

---

🌵Bug本是code常态，通过才是稀缺的意外！🌷

返回第一页☝

---

---

☕物有本末，事有终始，知所先后。🍭

🍎☝☝☝☝☝我的CSDN☝☝☝☝☝☝🍓