当前位置: 首页 > article >正文

【Java 优选算法】分治 - 快速排序

欢迎关注个人主页:逸狼


创造不易,可以点点赞吗~

如有错误,欢迎指出~



分治算法就是将一个问题划分为多个相同类型的子问题,解决这些子问题即解决该类问题 

颜色分类

题目链接

解法

利用三指针, i, left, right,将数组分为4个区间,如下图

三个指针的起始位置分别是

  1. left = -1 ,
  2. right = nums.length ,
  3. i =0 
  • 当nums[i]==0时,swap(nums[++left], nums[i++])
  • 当nums[i]==1时,i++;
  • 当nums[i]==2时,swap(nums[--right], nums[i]),记住此时的i还是未遍历元素,不能++

代码

class Solution {
    public void sortColors(int[] nums) {
        int n = nums.length;
        int i = 0, left = -1, right = n;
        while(i < right){
            if(nums[i] == 0) swap(nums, i++, ++left);
            else if(nums[i] == 1) i++;
            else swap(nums, --right, i);
        }
    }
    public void swap(int[] nums, int i, int j){
        int tmp = nums[i];
        nums[i] = nums[j];
        nums[j] = tmp;
    }
}

排序数组

题目链接

解法

利用上一题的"数组分三块"的思想实现快排.

随机取数组的一个key作为基准值,以此将数组分为三部分,即小于key,等于key,和大于key三部分.

此时只有小于key和大于key的部分是乱序的,后面使用递归将这两部分也排成有序部分.

优化: 取随机数r,可以计算基准值: key=num[r % (right - left + 1) + left]

代码

class Solution {
    public int[] sortArray(int[] nums) {
        qsort(nums, 0, nums.length - 1);
        return nums;
    }
    public void qsort(int[] nums, int l, int r){
        if(l >= r) return;

        //数组分三块
        int key = nums[new Random().nextInt(r - l + 1)+ l];
        int left = l - 1, right = r + 1, i = l;
        while(i < right){
            if(nums[i] < key) swap(nums, ++left, i++);
            else if(nums[i] == key) i++;
            else swap(nums, --right, i);
        }
        //[l,left],[left +1, right - 1][right, r]
        qsort(nums,l, left);
        qsort(nums,right,r);
    }
    public void swap(int[] nums, int i, int j){
        int tmp = nums[i];
        nums[i] = nums[j];
        nums[j] = tmp;
    }
}

数组中的第K个最大元素

题目链接

类似问题还有 前k大,前k小,第k大,第k小 问题 

解法

解法一: 使用堆,使用小根堆

解法二: 数组分三块 + 随机选择基准元素

题目要求的是取出第k大的元素,我们记为t 根据数组分三块思想将数组根据基准值key分为三部分,每个部分元素个数是a,b,c, 分下面三种情况

  1. 当c >= k时,说明 t 一定在区间[right, r]
  2. 当b+c >= k时,说明 t 一定是key
  3. 当b+c+a >= k 时,说明 t在区间[l, left]

代码

class Solution {

    public void swap(int[] nums, int i, int j){
        int t = nums[i];
        nums[i]= nums[j];
        nums[j] = t;
    }
    public int findKthLargest(int[] nums, int k) {
        
        return qsort(nums, 0, nums.length-1, k);
    }

    public int qsort(int[] nums,int l, int r, int k){
        if(l >= r) return nums[l];
        int left =l-1, i = l, right =r + 1, key = nums[new Random().nextInt(r - l + 1) + l];
        while(i < right){
            if(nums[i] < key) swap(nums, ++left, i++);
            else if(nums[i] == key) i++;
            else swap(nums, --right, i);
        }
        //计算每个区间的长度
        int a = left - l + 1, b = right - left - 1, c = r - right + 1;
        if(c >= k) return qsort(nums, right, r, k);
        else if( b + c >= k) return key;
        else return qsort(nums, l, left, k - b - c);
    }
}

库存管理|||

题目链接

解法

解法一: 排序,N*logN先将数组排序,再从小到大选择符合要求的元素

解法二:堆, N*log k ,建立一个大根堆

解法三: 快速选择算法,N, 随机选择基准元素+数组分三块,

下面展示解法三: 与上一题类似

代码

class Solution {
    public void swap(int[] nums, int i, int j){
        int tmp = nums[i];
        nums[i] = nums[j];
        nums[j] = tmp;
    }
    public int[] inventoryManagement(int[] stock, int cnt) {
        qsort(stock, 0, stock.length-1, cnt);
        int[] ret = new int[cnt];
        for(int i = 0; i < cnt; i++){
            ret[i] = stock[i];
        }
        return ret;

        
    }
    public void qsort(int[] nums, int l, int r, int k){
        if(l >= r) return;
        int left = l - 1, right = r + 1, i = l, key = nums[new Random().nextInt(r - l + 1) + l];
        while(i < right){
            if(nums[i] < key) swap(nums, ++left, i++);
            else if(nums[i] == key) i++;
            else swap(nums, --right, i);
        }
        int a = left - l + 1, b = right - left - 1, c = r - right + 1;
        if(a > k) qsort(nums, l, left, k);
        else if(a + b >= k) return;
        else qsort(nums, right, r, k - a - b);
    }
}


http://www.kler.cn/a/588036.html

相关文章:

  • 基于redis实现会话保持
  • Chat-Driven Business:灵活交互的新范式
  • python面向对象:封装的编程案例
  • 使用easyexcel实现单元格样式设置和下拉框设置
  • coze ai assistant Task 3
  • 【Django】【vue】设计一个评论模块
  • 【人工智能基础2】Tramsformer架构、自然语言处理基础、计算机视觉总结
  • 数字人本地部署之llama-本地推理模型
  • Skema:AI 驱动的方案到 BIM 加速工具,重塑早期设计工作流
  • superset部署记录
  • 奇安信二面
  • SpringMVC(六)异常:全局捕获与错误响应
  • Android (Kotlin) 高版本 DownloadManager 封装工具类,支持 APK 断点续传与自动安装
  • 【模拟面试】计算机考研复试集训(第五天)
  • 自然语言处理 | 文本清洗的20种核心策略:从数据噪声到信息价值
  • 7、标准库的string的常见使用
  • 加固脱壳技术:DEX动态加载对抗
  • Matlab 矢量控制和SVPWM的感应电机控制
  • 二.使用ffmpeg对原始音频数据重采样并进行AAC编码
  • 【Linux】learning notes(4)cat、more、less、head、tail、vi、vim