🌻算法,不如说它是一种思考方式🍀
算法专栏: 👉🏻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 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:
返回第一页☝
☕物有本末,事有终始,知所先后。🍭
🍎☝☝☝☝☝我的CSDN☝☝☝☝☝☝🍓