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

   🔥个人主页： 中草药

🔥专栏：【Java】登神长阶 史诗般的Java成神之路

🛍️一、912.排序数组

 题目链接：912. 排序数组 - 力扣（LeetCode）

代码

public class Solution5 {
    int[] tmp;
    public int[] sortArray(int[] nums) {
        tmp = new int[nums.length];
        merge(nums,0,nums.length-1);
        return nums;
    }
    public void merge(int[] nums,int left,int right){
        if(left>=right) return;
        //1.确定中间数
        int mid = left+(right-left)/2;
        //2.后序遍历 给左右两个数组排个序
        merge(nums,left,mid);
        merge(nums,mid+1,right);
        //3.合并两个有序数组
        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.还原
        for(int j=left;j<=right;j++){
            nums[j]=tmp[j-left];
        }
    }
}

算法原理

        这段 Java 代码实现了使用归并排序算法对给定整数数组进行排序的功能。归并排序是一种分治算法，其主要思想是将数组不断地分割成较小的子数组，直到每个子数组只有一个元素，然后再将这些子数组合并成有序的数组。

1. 确定中间数：

   • 在merge方法中，首先通过int mid = left+(right-left)/2;计算当前要处理的子数组的中间位置。这种计算方式可以避免直接使用(left + right) / 2可能导致的整数溢出问题。

2. 后序遍历，给左右两个数组排序：

   • 通过递归调用merge(nums, left, mid);和merge(nums, mid + 1, right);分别对左子数组和右子数组进行排序。这一步体现了归并排序的分治思想，不断将问题分解为更小的子问题进行求解。

3. 合并两个有序数组：

   • 比较左子数组和右子数组的当前元素，将较小的元素放入临时数组tmp中。具体实现是通过一个循环while(cur1<=mid && cur2<=right)，在这个循环中，如果nums[cur1] <= nums[cur2]，则将nums[cur1]放入tmp，并将cur1指针后移；否则，将nums[cur2]放入tmp，并将cur2指针后移。
   • 当其中一个子数组的元素全部放入tmp后，可能还有另一个子数组有剩余元素，通过两个额外的循环while(cur1<=mid)和while(cur2<=right)分别处理左子数组和右子数组的剩余元素，将它们依次放入tmp。

4. 还原：

   • 最后，将临时数组tmp中的元素复制回原数组nums中，通过循环for(int j=left;j<=right;j++)实现。这里nums[j]=tmp[j-left];是根据原数组的起始位置和临时数组的相对位置进行赋值的。

这就是典型的归并排序，注意处理未完的数组，还有还原这一步骤

🧥二、LCR 170.交易逆序对的总数

题目链接：LCR 170. 交易逆序对的总数 - 力扣（LeetCode）

代码

public class Solution6 {
    int[] tmp;
    public int reversePairs(int[] record) {
        tmp = new int[record.length];
        return merge(record,0,record.length-1);
    }
    public int merge(int[] record, int left, int right) {
        if(left>=right)return 0;
        int mid = (right+left)/2;
        int ret=0;
        ret+=merge(record,left,mid);
        ret+=merge(record,mid+1,right);
        int cur1=left,cur2=mid+1,i=0;
        while(cur1<=mid && cur2<=right){
            if(record[cur1]<=record[cur2]){
                tmp[i++]=record[cur1++];
            }else{
                tmp[i++]=record[cur2++];
                //归并排序为升序，找出比我(cur2)大的
                ret+=mid-cur1+1;
            }
        }
        while(cur1<=mid){
            tmp[i++]=record[cur1++];
        }
        while(cur2<=right){
            tmp[i++]=record[cur2++];
        }
        for (int j = left; j <=right ; j++) {
            record[j]=tmp[j-left];
        }
        return ret;
    }

    public int merge2(int[] record, int left, int right) {
        if(left>=right)return 0;
        int mid = (right+left)/2;
        int ret=0;
        ret+=merge(record,left,mid);
        ret+=merge(record,mid+1,right);
        int cur1=left,cur2=mid+1,i=0;
        while(cur1<=mid && cur2<=right){
            if(record[cur1]<=record[cur2]){
                tmp[i++]=record[cur2++];
            }else{
                tmp[i++]=record[cur1++];
                //归并排序为降序，找出比我(cur1)小的
                ret+=right-cur2+1;
            }
        }
        while(cur1<=mid){
            tmp[i++]=record[cur1++];
        }
        while(cur2<=right){
            tmp[i++]=record[cur2++];
        }
        for (int j = left; j <=right ; j++) {
            record[j]=tmp[j-left];
        }
        return ret;
    }
}

算法原理 

        这段 Java 代码实现了计算给定数组中 “交易逆序对的总数” 的功能，使用了归并排序的思想。归并排序是一种分治算法，通过将数组不断地分割成较小的子数组，然后再将这些子数组合并成有序的数组，在合并的过程中计算逆序对的数量。        

1. 初始化和递归调用：

   • 首先定义了一个临时数组tmp，用于在归并过程中存储排序后的子数组。
   • 在reversePairs方法中，调用merge方法并传入数组和起始、结束索引，开始计算逆序对的总数。
   • 在merge方法中，如果子数组的长度为 1 或更小时（left>=right），直接返回 0，表示没有逆序对。
   • 否则，将数组分成左右两部分，分别递归调用merge方法计算左子数组和右子数组中的逆序对数量，并将结果累加到ret变量中。

2. 合并两个有序子数组并计算逆序对数量：

   • 使用指针cur1和cur2分别指向左子数组和右子数组的起始位置，同时定义一个指针i用于指向临时数组tmp的当前位置。
   • 在循环while(cur1<=mid && cur2<=right)中，比较左子数组和右子数组的当前元素：
     • 如果record[cur1]<=record[cur2]，将左子数组的当前元素放入临时数组tmp中，并将cur1指针后移。
     • 如果record[cur1]>record[cur2]，将右子数组的当前元素放入临时数组tmp中，并将cur2指针后移，同时计算逆序对的数量。这里的思路是，因为归并排序是升序排序，当右子数组的当前元素小于左子数组的当前元素时，左子数组中从当前指针cur1到mid的所有元素都与右子数组的当前元素构成逆序对，所以逆序对数量为ret+=mid-cur1+1。
   • 当其中一个子数组的元素全部放入tmp后，通过两个额外的循环处理左子数组和右子数组的剩余元素，将它们依次放入tmp。

3. 还原数组：

   • 最后，将临时数组tmp中的元素复制回原数组record中，通过循环for (int j = left; j <= right; j++)实现，这里record[j]=tmp[j-left];是根据原数组的起始位置和临时数组的相对位置进行赋值的。

4. merge2方法与merge方法类似，但在合并子数组时是按照降序进行排序，并在计算逆序对数量时的逻辑略有不同：

   • 当record[cur1]>record[cur2]时，将左子数组的当前元素放入临时数组tmp中，并将cur1指针后移，同时计算逆序对的数量为ret+=right-cur2+1，因为此时是降序排序，当左子数组的当前元素大于右子数组的当前元素时，右子数组中从当前指针cur2到right的所有元素都与左子数组的当前元素构成逆序对。

注意，降序和升序的思路是不一样的，注意ret+=的条件不一样

👢三、315.计算右侧小于当前元素的个数

题目链接：315. 计算右侧小于当前元素的个数 - 力扣（LeetCode）

代码

import java.util.ArrayList;
import java.util.List;

public class Solution7 {
    int[] ret;
    int[] index;
    int[] tmpNums;
    int[] tmpIndex;

    /**
     * 315.计算右侧小于当前元素的个数
     * @param nums
     * @return
     */
    public List<Integer> countSmaller(int[] nums) {
        ret = new int[nums.length];
        index = new int[nums.length];
        tmpNums = new int[nums.length];
        tmpIndex = new int[nums.length];
        for (int i = 0; i < nums.length; i++) {
            index[i] = i;
        }
        merge(nums,0,nums.length-1);
        List<Integer> list = new ArrayList<Integer>();
        for(int x:ret){
            list.add(x);
        }
        return list;
    }

    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);

        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];
        }
    }
}

算法原理 

        这段 Java 代码实现了计算给定整数数组中每个元素右侧小于当前元素的个数的功能。它使用了归并排序的思想，在归并的过程中进行计数操作。

1. 初始化和准备工作：

   • 定义了四个数组ret、index、tmpNums和tmpIndex。ret数组用于存储每个元素右侧小于当前元素的个数；index数组用于记录原始数组中元素的索引；tmpNums和tmpIndex是在归并过程中临时使用的数组。
   • 在countSmaller方法中，首先初始化ret和index数组，并为index数组赋值为对应元素在原始数组中的索引。然后调用merge方法进行归并排序并计算结果，最后将ret数组中的结果转换为List<Integer>类型返回。

2. 归并排序和计数过程：

   • 在merge方法中，如果子数组的长度为 1 或更小时（left>=right），直接返回，因为此时不需要进行归并和计数操作。
   • 否则，将数组分成左右两部分，分别递归调用merge方法对左子数组和右子数组进行排序和计数。
   • 在合并两个有序子数组的过程中，使用指针cur1和cur2分别指向左子数组和右子数组的起始位置，同时定义一个指针i用于指向临时数组的当前位置。
   • 在循环while(cur1<=mid && cur2<=right)中，比较左子数组和右子数组的当前元素：
     • 如果nums[cur1]<=nums[cur2]，将右子数组的当前元素放入临时数组tmpNums中，并将对应的索引放入tmpIndex中，然后将cur2指针后移。
     • 如果nums[cur1]>nums[cur2]，此时说明左子数组中当前元素nums[cur1]右侧有right - cur2 + 1个小于它的元素，将这个数量累加到ret[index[cur1]]中。然后将左子数组的当前元素放入临时数组tmpNums中，并将对应的索引放入tmpIndex中，最后将cur1指针后移。
   • 当其中一个子数组的元素全部放入临时数组后，通过两个额外的循环处理左子数组和右子数组的剩余元素，将它们依次放入临时数组。
   • 最后，将临时数组中的元素复制回原数组nums和index数组中。

注意对全局变量的使用，index数组的目的是保证，在排序过程中，跟着数字的位置移动，下标不会动，然后通过ret去记录

👟四、493.翻转对

题目链接：493. 翻转对 - 力扣（LeetCode）

代码

public class Solution8 {
    int[] tmp;
    public int reversePairs(int[] nums) {
        tmp=new int[nums.length];
        int ret=merge(nums,0,nums.length-1);
        return ret;
    }
    public int merge(int[] nums, int left, int right) {
        if(left>=right)return 0;
        int mid=(right+left)/2;
        int ret=0;
        ret+=merge(nums,left,mid);
        ret+=merge(nums,mid+1,right);
        int cur1=left,i=left,cur2=mid+1;
        //先解决问题 注意if条件
        while(cur1<=mid){
            while(cur2<=right&&nums[cur1]/2.0<=nums[cur2])cur2++;
            if(cur2>right){
                break;
            }
            ret+=right-cur2+1;
            cur1++;
        }
        cur1=left;cur2=mid+1;
        //找小--降序
        while(cur1<=mid&&cur2<=right){
            tmp[i++]=nums[cur1]<=nums[cur2]?nums[cur2++]: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];
        }
        return ret;
    }
}

算法原理 

        这段 Java 代码实现了计算给定整数数组中 “翻转对” 的数量的功能，使用了归并排序的思想。“翻转对” 指的是满足 i < j 且 nums[i] > 2 * nums[j] 的数对 (i, j)。

1. 初始化和递归调用：

   • 首先定义了一个临时数组tmp，用于在归并过程中存储排序后的子数组。
   • 在reversePairs方法中，调用merge方法并传入数组和起始、结束索引，开始计算翻转对的总数。
   • 在merge方法中，如果子数组的长度为 1 或更小时（left>=right），直接返回 0，表示没有翻转对。
   • 否则，将数组分成左右两部分，分别递归调用merge方法计算左子数组和右子数组中的翻转对数量，并将结果累加到ret变量中。

2. 计算翻转对数量：

   • 使用指针cur1指向左子数组的起始位置，在循环while(cur1<=mid)中，对于左子数组的每个元素nums[cur1]，使用指针cur2在右子数组中查找满足条件nums[cur1]/2.0<=nums[cur2]的位置。当找到这样的位置时，说明从这个位置到右子数组的末尾都与当前左子数组元素构成翻转对，所以将right - cur2 + 1累加到ret变量中。然后将cur1指针后移，继续查找下一个左子数组元素的翻转对。

3. 合并两个有序子数组：

   • 再次使用指针cur1和cur2分别指向左子数组和右子数组的起始位置，同时定义一个指针i用于指向临时数组tmp的当前位置。
   • 在循环while(cur1<=mid&&cur2<=right)中，比较左子数组和右子数组的当前元素：
     • 如果nums[cur1]<=nums[cur2]，将右子数组的当前元素放入临时数组tmp中，并将cur2指针后移。
     • 如果nums[cur1]>nums[cur2]，将左子数组的当前元素放入临时数组tmp中，并将cur1指针后移。
   • 当其中一个子数组的元素全部放入tmp后，通过两个额外的循环处理左子数组和右子数组的剩余元素，将它们依次放入tmp。

4. 还原数组：

   • 最后，将临时数组tmp中的元素复制回原数组nums中，通过循环for (int j = left; j <= right; j++)实现，这里nums[j]=tmp[j];是根据原数组的起始位置和临时数组的相对位置进行赋值的。

这里，运用了归并排序的思路，但是更主要的还是针对此问题，用双指针的逻辑去处理问题