算法通关村第十关-白银挑战数组最大K数

大家好我是苏麟 , 今天带来一道应用快排的题 .

数组中的第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;
    }
}