栏目分类:
子分类:
返回
名师互学网用户登录
快速导航关闭
当前搜索
当前分类
子分类
实用工具
热门搜索
名师互学网 > IT > 软件开发 > 后端开发 > Java

数组中的第K个最大元素

Java 更新时间: 发布时间: IT归档 最新发布 模块sitemap 名妆网 法律咨询 聚返吧 英语巴士网 伯小乐 网商动力

数组中的第K个最大元素

数组中的第K个最大元素
  • 快速排序
    • 算法思路
  • 二路归并排序
    • 算法思路
  • 堆排序
    • 算法思路

本质上就是排序算法

快速排序 算法思路
  • 快速排序思想来源于双指针,将哨兵结点的值放置于指定位置,使得该位置左侧均小于等于哨兵节点,右侧均大于等于哨兵节点。因此,为将哨兵节点值放在指定位置,需先对其进行保存。并按照从右向左,赋空位值。从左向右,赋空位值。左右指针的最后一次移动会带来空位,将哨兵填充置此位置,并返回哨兵坐标,进行分治。
  • 由此,代码模板如下:
class Solution {
    public int findKthLargest(int[] nums, int k) {
        int i=0,j=nums.length-1;
        quickSort(nums,i,j);
        return nums[nums.length-k];
   
    }
    public void quickSort(int[] nums,int i,int j){
        if(i>=j){
            return;
        }

        int privot = privotSort(nums,i,j);
        quickSort(nums,i,privot-1);
        quickSort(nums,privot+1,j);
    }

    public int privotSort(int[] nums,int i,int j){
        int temp = nums[i];
        // 注意我的边界条件均没有取等号,当遇见与哨兵值相同时,需要判断,左右指针是否仍然保持左右位置,如果保持相对关系,则可对空位赋值。
        while(itemp){
                j--;
            }
            if(i 
二路归并排序 
算法思路 
  • 首先理解,二路归并排序,是分治递归算法,需要开辟额外数组。从中间进行分治递归,将其切成最小的两个单位后,对其进行排序。通过递归回溯,将两个内部排序完成后的数组进行合并。
  • 由此,代码模板如下:
class Solution {
    public int findKthLargest(int[] nums, int k) {
        // 二路归并排序

        int len = nums.length;
        int[] numbers = mergeSort(nums,len);
        return numbers[len-k];
    }

    public int[] mergeSort(int[] nums,int len){
        if(len<2){
            return nums;
        }
        int mid = len/2;
        int[] leftNums = Arrays.copyOfRange(nums,0,mid);
        int[] rightNums = Arrays.copyOfRange(nums,mid,len);

        return merge(mergeSort(leftNums,leftNums.length),mergeSort(rightNums,rightNums.length));
    }

    public int[] merge(int[] nums1,int[] nums2){
        int len1= nums1.length;
        int len2 = nums2.length;
        int[] nums = new int[len1+len2];
        int i=0,j=0,k=0;
        for(;k=len1||(j=nums2[j])){
                nums[i+j] = nums2[j];
                j++;
            }else{
                nums[i+j] = nums1[i];
                i++;
            }
        }
        return nums;
    }
   
}
堆排序 算法思路
  • 一般考察大顶堆,即父节点值大于左右子节点值。排序步骤,一般从第一个非叶子节点(n/2-1)开始,自上而下,将较大值向上取。再自下而上,调整至根节点,保证更根节点为最大值,且父节点均大于左右节点。将最大值从根节点获取后,将其按照调整位置进行数组的置换,再对根节点进行调整。
  • 由此,算法模板如下:
class Solution {
    public int findKthLargest(int[] nums, int k) {
        int len = nums.length;
        heapSort(nums,len);
        return nums[len-k];
    }


    // 堆排序
    public void heapSort(int[] nums,int len){
        
        // 从第一个非叶子节点调整一次
        for(int i =len/2-1;i>=0;i--){
            adjustHeap(nums,i,len);
        }
        // 交换len-1次
        for(int i=len-1;i>0;i--){
            // 始终交换最大值置数组末尾
            swap(nums,0,i);
            // 相当于删除树上一些节点,已经排序完成的,不需要再参与调整
            adjustHeap(nums,0,i);
        }

    }

    // 从当前位置向下到根节点进行最大值调整
    public void adjustHeap(int[] nums,int root,int end){

        // 标记位
        int index = root;
        // 左右节点
        int left = root*2+1;
        int right = root*2+2;
        // 右节点存在,且值大于最大节点
        if(rightnums[index]){
            index = right;
        }

        // 左节点存在,且值大于最大节点
        if(leftnums[index]){
            index = left;
        }

        // 递归出口
        if(index == root){
            return ;
        }

        swap(nums,root,index);
        // 递归向下处理
        adjustHeap(nums,index,end);

    }

    public void swap(int[] nums,int i,int j){
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }


   
}
转载请注明:文章转载自 www.mshxw.com
本文地址:https://www.mshxw.com/it/963918.html
我们一直用心在做
关于我们 文章归档 网站地图 联系我们

版权所有 (c)2021-2022 MSHXW.COM

ICP备案号:晋ICP备2021003244-6号