技术博客
首页 所有文章 标签 分类 关于
技术博客

目录

-Java-优选算法分治-归并排序

 收录于 未分类
   约 1676 字   预计阅读 4 分钟 
https://bing.ee123.net/img/rand?artid=146236829

【Java 优选算法】分治-归并排序

https://i-blog.csdnimg.cn/direct/ca81952022a44dd28d34fa96c8ab2136.jpeg

欢迎关注个人主页：

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

如有错误，欢迎指出~

数组分块如二叉树的前序遍历, 而归并排序就如二叉树的后序遍历

https://i-blog.csdnimg.cn/direct/ec4c8a3255a94083b13708143eaa9fd3.png

https://i-blog.csdnimg.cn/direct/9517cdc5eb4840468d3392a4854af713.png

解法

使用归并算法

  1. 根据中间点划分区间, mid =(right + left ) / 2
  2. 将左右区间排序
  3. 合并两个有序数组
  4. 处理没有遍历完的数组
  5. 将排好序的数组tmp覆盖到原数组nums里

优化: 将tmp数组new成一个全局变量,减少频繁的空间开销

代码

class Solution {
    int[] tmp;
    public int[] sortArray(int[] nums) {
        int n = nums.length;
        tmp = new int[n];
        mergeSort(nums, 0, n - 1);
        return nums;
    }
    public void mergeSort(int[] nums, int left, int right){
        if(left >= right) return;

        //1.找到中间点mid
        int mid = (left + right) / 2;
        //2.左右排好序
        mergeSort(nums, left, mid);
        mergeSort(nums, mid + 1, right);
        //3.合并有序数组 [left, mid] [mid + 1, right]
        int cur1 = left, cur2 = mid + 1, i = 0;
        while(cur1 <= mid && cur2 <= right){
            tmp[i++] = nums[cur1] <= nums[cur2] ? nums[cur1++] : nums[cur2++];
        }
        //处理没有遍历完的数组
        while(cur1 <= mid) tmp[i++] = nums[cur1++];
        while(cur2 <= right) tmp[i++] = nums[cur2++];
        //4.tmp覆盖nums
        for(int j = left; j <= right; j++){
            nums[j] = tmp[j - left];
        }
    }
}

（数组中的逆序对）

https://i-blog.csdnimg.cn/direct/8380c00db2424eb7912614513f4e776b.png

解法

解法一: 暴力枚举: 两层for循环

解法二: 分治,N*logN

将数组通过mid分为两部分,

  1. 先找左半部分的逆序对, 再左排序
  2. 再找右半部分的逆序对, 再右排序
  3. 最后找一左一右组合的逆序对(此时 左数组和右数组分别都是有序的 ),再合并排序

策略一: 找出该数(nums[cur1] )之前,有多少个(mid - cur2 + 1)数比我(nums[cur2] )大.

  • 当nums[cur1] <= nums[cur2] 时 , cur1++;
  • 当nums[cur1] > nums[cur2]时 ,ret += mid - cur1 + 1, cur2++

https://i-blog.csdnimg.cn/direct/9f51c36c34ef4731a7cad78b51ff6dad.png

策略二: 找出该数(nums[cur1] )之后,有多少个(right - cur2 + 1)数比我(nums[cur2] )小.

  • 当nums[cur1] <= nums[cur2] 时 , cur2++;
  • 当nums[cur1] > nums[cur2]时 ,ret += right - cur2 + 1, cur1++

https://i-blog.csdnimg.cn/direct/ff589d2c87e24d898fbad09c3e0111b2.png

  • 时间复杂度 ：O(nlogn)，这是归并排序的时间复杂度，其中 n 是数组的长度。
  • 空间复杂度 ：O(n)，主要是临时数组 tmp 的空间开销。

代码

class Solution {
    int[] tmp;
    public int reversePairs(int[] nums) {
        int n = nums.length;
        tmp = new int[n];
        return merge(nums, 0, n - 1);
    }
    public int merge(int[] nums, int left, int right){
        if(left >= right) return 0;
        //找出中间点mid
        int mid = (left + right) / 2;
        int ret = 0;
        //左右排好序,返回结果
        ret += merge(nums, left, mid);
        ret += merge(nums, mid + 1, right);

        //合并有序数组,计算一左一右逆序对
        int cur1 = left, cur2 = mid + 1, i = 0;
        while(cur1 <= mid && cur2 <= right){
            if(nums[cur1] <= nums[cur2]){
                tmp[i++] = nums[cur1++];
            }else{
                ret += mid - cur1 + 1;
                tmp[i++] = nums[cur2++];
            }
            
        }
        //处理剩下的数组
        while(cur1 <= mid) tmp[i++] = nums[cur1++];
        while(cur2 <= right) tmp[i++] = nums[cur2++];

        for(int j = left; j <= right; j++){
            nums[j] = tmp[j - left];
        }
        return ret;

    }
}

https://i-blog.csdnimg.cn/direct/52585ca0ddbb431785d89ef93b697021.png

解法

解法: 归并排序

和上一题类似,但是这里只能通过策略二: 降序解决

https://i-blog.csdnimg.cn/direct/b2c2347ae38f475db08a7f6913ab4874.png

注意: 最终结果是加在原始数组的下标中

代码

class Solution {
    int[] ret;
    int[] index; //标记 nums中当前元素的原始下标
    int[] tmpIndex;
    int[] tmpNums;

    public List<Integer> countSmaller(int[] nums) {
        int n = nums.length;
        ret = new int[n];
        index = new int[n];
        tmpIndex = new int[n];
        tmpNums = new int[n];
        //初始化index数组
        for(int i = 0; i < n; i++){
            index[i] = i;
        }
        merge(nums, 0, n - 1);
        List<Integer> l = new ArrayList<>();
        for(int x : ret){
            l.add(x);
        }
        return l;
    }
    public void merge(int[] nums, int left, int right){
        if(left >= right) return;
        int mid = (left + right) / 2;
        merge(nums, left, mid);
        merge(nums, mid + 1, right);
        //[left, mid] [mid + 1, right] 处理一左一右的情况
        int cur1 = left, cur2 = mid + 1, i = 0;
        while(cur1 <= mid && cur2 <= right){//降序排列
            if(nums[cur1] <= nums[cur2]){
                tmpNums[i] = nums[cur2];
                tmpIndex[i++] = index[cur2++];//下标数组同步修改
            }else{
                ret[index[cur1]] += right - cur2 + 1;//结果在原数组下标对应值位置上
                tmpNums[i] = nums[cur1];
                tmpIndex[i++] = index[cur1++];
            }
        }
        while(cur1 <= mid) {
            tmpNums[i] = nums[cur1];
            tmpIndex[i++] = index[cur1++];

        }
        while(cur2 <= right){
            tmpNums[i] = nums[cur2];
            tmpIndex[i++] = index[cur2++];
        } 

        for(int j = left; j <= right; j++){
            nums[j] = tmpNums[j - left];
            index[j] = tmpIndex[j - left];
        }
    }
}

https://i-blog.csdnimg.cn/direct/e3ba3cc481454a42854f022a8f7064e2.png

解法

https://i-blog.csdnimg.cn/direct/e17b0525c8bd4a40b3f9296c0015b14c.png

注意: 要先统计结果后,再进行排序

边界情况, 可以将2倍的数转为long,也可以使用 / 2.0

代码

策略一: 降序,谁大谁在前面

class Solution {
    int[] tmp; 
    public int reversePairs(int[] nums) {
     int n = nums.length;
        tmp = new int[n];
        return merge(nums, 0, n - 1);
    }
    public int merge(int[] nums, int left, int right){
        if(left >= right) return 0;
        int mid = (left + right) / 2, ret = 0;

        ret += merge(nums, left, mid);
        ret += merge(nums, mid + 1, right);
        //[left, mid] [mid + 1, right]
        //先统计,后归并
        int x = left, y = mid + 1;
        while(x <= mid && y <= right){//降序
            if(nums[x] / 2.0 > nums[y] ){
                ret += right - y + 1;
                x++;
            }else{                
                y++;
            }
        }
        
        int cur1 = left, cur2 = mid + 1, i = 0;
        while(cur1 <= mid && cur2 <= right){
            if(nums[cur1] <= nums[cur2]){
                tmp[i++] = nums[cur2++];
            }else{                
                tmp[i++] = nums[cur1++];
            }
        }
        while(cur1 <= mid) tmp[i++] = nums[cur1++];
        while(cur2 <= right) tmp[i++] = nums[cur2++];

        for(int j = left; j <= right; j++){
            nums[j] = tmp[j - left];
        }
        return ret;
    }
}

策略二: 升序

class Solution {
    int[] tmp; 
    public int reversePairs(int[] nums) {
     int n = nums.length;
        tmp = new int[n];
        return merge(nums, 0, n - 1);
    }
    public int merge(int[] nums, int left, int right){
        if(left >= right) return 0;
        int mid = (left + right) / 2, ret = 0;

        ret += merge(nums, left, mid);
        ret += merge(nums, mid + 1, right);
        //[left, mid] [mid + 1, right]
        //先统计,后归并
        int x = left, y = mid + 1;
        while(x <= mid && y <= right){//降序
            if(nums[x] / 2.0 > nums[y] ){
                ret += mid - x + 1;
                y++;
            }else{                
                x++;
            }
        }
        
        int cur1 = left, cur2 = mid + 1, i = 0;
        while(cur1 <= mid && cur2 <= right){
            if(nums[cur1] <= nums[cur2]){
                tmp[i++] = nums[cur1++];
            }else{                
                tmp[i++] = nums[cur2++];
            }
        }
        while(cur1 <= mid) tmp[i++] = nums[cur1++];
        while(cur2 <= right) tmp[i++] = nums[cur2++];

        for(int j = left; j <= right; j++){
            nums[j] = tmp[j - left];
        }
        return ret;
    }
}
更新于 2025-03-16
 算法
返回 | 主页