【算法】【优选算法】分治（下）

目录

• 一、归并排序
• 二、LCR170.交易逆序对的总数
• 三、315.计算右侧⼩于当前元素的个数
• 四、493.翻转对

一、归并排序

题目链接：归并排序
题目描述：

题目解析：

• 就是排序数组。

解题思路：

• 分：将数组⼀分为⼆为两部分，⼀直分解到数组的⻓度为1 ，使整个数组的排序过程被分为「左半部分排序」+「右半部分排序」；
• 治：将两个较短的「有序数组合并成⼀个⻓的有序数组」，⼀直合并到最初的⻓度。

解题代码：

//时间复杂度：O(NlogN)
//空间复杂度：O(n)
class Solution {
    int[] tmp;
    
    public int[] sortArray(int[] nums) {
        tmp = new int[nums.length];
        mergeSort(nums,0,nums.length-1);
        return nums;
    }
    //归并排序
    public void mergeSort(int[] nums, int l, int r) {
        if(l >= r) return;
        int left = l;
        int right = r;
        int mid = (left + right) / 2;
        //分
        mergeSort(nums, l, mid);
        mergeSort(nums, mid+1, r);

        //治：合并两个有序数组
        int cur1 = left;
        int cur2 = mid + 1;
        int i = left;
        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];
        }
        
    }
}

二、LCR170.交易逆序对的总数

题目链接：LCR170.交易逆序对的总数
题目描述：

题目解析：

• 逆序对：逆序对就是指，在该数组元素之后与比它小的元素组成的两个数字，就称为一个逆序对，返回数组中逆序对总数。

2.1 分治思想

解题思路：

• 其实我们可以将数组分为两段，那么数组的总逆序对和等于：两段子数组的逆序对和 + 前面一段数组中每个元素在后面一段元素组成的逆序对和（就是遍历前面一段数组，在后面一段数组中找比该元素小的元素个数）（简称为一左一右选逆序对）。
  

• 两段子数组的逆序对和，我们可以通过递归实现。

• 那么我们的核心就是求一左一右选取逆序对的和。

• 直接去遍历求解，复杂度还是高，如果我们将两段子数组排序，那么我们就有两种方式简单求了。

• • 升序排序：我们就找前一个子数组中大的元素个数即可（就当nums[ cur2 ] < nums[ cur1 ]时统计即可），即[cur1 , mid]。如果求后一个数组小元素，会有重复。
    
• • 降序排序：我们就找后一个数组中小的元素个数即可（就当nums[ cur2 ] < nums[ cur1 ]时统计即可），即[ mid+1 , right ]。如果求前一个数组大元素，会有重复。
    

• 看上面的就是与归并排序的逻辑一摸一样的。

解题代码：

//时间复杂度：O(NlogN)
//空间复杂度：O(n)
//升序版本：
class Solution {
    int[] tmp;
    public int reversePairs(int[] nums) {
        int n = nums.length;
        tmp = new int[n];
        return merageSort(nums, 0, n-1);
    }
    public int merageSort(int[] nums, int left, int right) {
        if(left >= right) return 0;
        int ret = 0;
        int mid = (left + right) / 2;
		//分:两段子数组的逆序对和
        ret += merageSort(nums, left, mid);
        ret += merageSort(nums, mid + 1, right);
		//治：合并两个有序数组 + 统计一左一右逆序对个数
        int cur1 = left, cur2 = mid + 1;
        int i = left;
        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];
        return ret;
    }
}

//时间复杂度：O(NlogN)
//空间复杂度：O(n)
//降序版本：
class Solution {
    int[] tmp;
    public int reversePairs(int[] nums) {
        int n = nums.length;
        tmp = new int[n];
        return merageSort(nums, 0, n-1);
    }
    public int merageSort(int[] nums, int left, int right) {
        if(left >= right) return 0;
        int ret = 0;
        int mid = (left + right) / 2;
		//分:两段子数组的逆序对和
        ret += merageSort(nums, left, mid);
        ret += merageSort(nums, mid + 1, right);
		//治：合并两个有序数组 + 统计一左一右逆序对个数
        int cur1 = left, cur2 = mid + 1;
        int i = left;
        while(cur1 <= mid && cur2 <= right) {
            if(nums[cur1] <= nums[cur2]) tmp[i++] = nums[cur2++];
            else {
                ret += (right - cur2 +1);
                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];
        return ret;
    }
}

2.2 暴力枚举

解题思路：

• 直接两个for循环，将第一层遍历数组，第二层遍历后续元素比该元素小的数组个数。
• 会超时。

解题代码：

//时间复杂度：O(n^2)
//空间复杂度：O(1)
class Solution {
    public int reversePairs(int[] record) {
        int ret = 0;
        for(int i = 0; i < record.length; i++) {
            for(int j = i +1; j < record.length; j++) {
                if(record[i] > record[j]) ret++;
            }
        }
        return ret;
    }
}

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

题目链接：315.计算右侧⼩于当前元素的个数
题目描述：

题目解析：

• 这道题其实跟上一题是差不多的，但是这个是记录下当前元素后面比它小的元素的个数，并存在一个数组的下标相同的位置。
• 最后返回存个数的数组。

3.1 分治思想

解题思路：

• 这道题跟上一道的解题思路是一模一样的，将数组分为两段。每个下标的数组的对应值等于：前一段个数+后一段个数。
• 由于求小的个数，所以我们使用降序求法，使用升序需要考虑边界情况。
• 当nums[ cur2 ] < nums[ cur1 ]时统计[ mid+1 , right ]个数，放入结果数组的nums[ cur1 ]对应下标位置即可。
• 我们要将数组中的值与其下标对应，由于数组中元素可以重复，所以不能使用哈希表，我们再使用一个数组记录每个元素的下标，两个数组绑定，同时移动。
• 下标数组的移动和原数组的移动是一模一样的，所以合并是也需要引入临时数组。

解题代码：

//时间复杂度：O(NlogN)
//空间复杂度：O(n)
//降序版本：
class Solution {
    int[] tmpNums;
    int[] tmpIndex;
    int[] ret;
    int[] index;

    public List<Integer> countSmaller(int[] nums) {
        int n = nums.length;
        tmpIndex = new int[n];
        tmpNums = new int[n];
        ret = new int[n];
		//下标数组
        index = new int[n];
        for(int i = 0; i < n; i++) 
            index[i] = i; 

        mergeSort(nums, 0, n-1);

        List<Integer> list = new ArrayList<>();
        for(int x : ret)
            list.add(x);
        return list;
    }
    public void mergeSort(int[] nums, int left, int right) {
        if(left >= right) return;
        int mid = (left + right) / 2;
		//分:两段子数组
        mergeSort(nums, left, mid);
        mergeSort(nums, mid+1, right);
		//治：合并两个有序数组，下标数组同时合并 + 统计个数
        int cur1 = left, cur2 = mid + 1;
        int i = left;
        while(cur1 <= mid && cur2 <= right) {
            if(nums[cur2] >= nums[cur1]) {
                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];
            index[j] = tmpIndex[j];
        }
    }
}

3.2 暴力枚举

解题思路：

• 两层for循环即可
• 会超时

解题代码：

//时间复杂度：O(n^2)
//空间复杂度：O(1)
class Solution {
    public List<Integer> countSmaller(int[] nums) {
        List<Integer> ret = new ArrayList<>();
        for(int i = 0; i < nums.length; i++) {
            int a = 0;
            for(int j = i + 1; j < nums.length; j++) {
                if(nums[j] < nums[i]) a++;
            }
            ret.add(a);
        }
        return ret;
    }
}

四、493.翻转对

题目链接：493.翻转对
题目描述：

题目解析：

• 题目非常清晰，并不用解析。

4.1 分治思想

解题思路：

• 我们依旧是将数组分为两段：那么数组的总翻转对和等于：两段子数组的翻转对和 + 前面一段数组中每个元素在后面一段元素组成的翻转对和（就是遍历前面一段数组，在后面一段数组中找比该元素一半小的元素个数）（简称为一左一右选翻转对）。
• 依旧可以是分升序和降序来求：
• • 升序排序：立足cur2，我们就找前一个子数组中大的元素个数即可，即[cur1 , mid]。
• • 降序排序：立足cur1，我们就找后一个数组中小的元素个数即可，即[ mid+1 , right ]。
• 但是由于我们的判断条件与合并是不一样的，所以单独写一个循环来计算。
• 每个元素不会超出int范围，但是乘2就有可能会超出，所以判断条件写 nums[cur1] / 2.0 <= nums[cur2]

解题代码：

//时间复杂度：O(NlogN)
//空间复杂度：O(n)
//升序版本：
class Solution {
    int[] tmp;
    public int reversePairs(int[] nums) {
        tmp = new int[nums.length];
        return mergeSort(nums,0,nums.length-1);

    }
    public int mergeSort(int[] nums, int left, int right) {
        if(left >= right) return 0;
        int mid = (left + right) / 2;
        int ret = 0;
        //分:两段子数组的翻转对和
        ret += mergeSort(nums, left, mid);
        ret += mergeSort(nums, mid+1, right);
		//统计一左一右逆序对个数
        int cur1 = left, cur2 = mid + 1;
        int i = left;
        while(cur2 <= right) {
            while(cur1 <= mid && nums[cur1] / 2.0 <= nums[cur2] ) cur1++;
            if(cur1 > mid) break;
            ret += (mid - cur1 + 1);
            cur2++;
        }
		//治：合并两个有序数组
        cur1 = left;
        cur2 = mid + 1;
        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];
        }
        return ret;
    }
}
//时间复杂度：O(NlogN)
//空间复杂度：O(n)
//降序版本：
class Solution {
    int[] tmp;
    public int reversePairs(int[] nums) {
        tmp = new int[nums.length];
        return mergeSort(nums,0,nums.length-1);

    }
    public int mergeSort(int[] nums, int left, int right) {
        if(left >= right) return 0;
        int mid = (left + right) / 2;
        int ret = 0;
         //分:两段子数组的翻转对和
        ret += mergeSort(nums, left, mid);
        ret += mergeSort(nums, mid+1, right);
		//统计一左一右逆序对个数
        int cur1 = left, cur2 = mid + 1;
        int i = left;
        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) {
            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];
        }
        return ret;
    }
}

4.2 暴力枚举

解题思路：

• 直接两层for循环即可
• 会超时

解题代码：

//时间复杂度：O(n^2)
//空间复杂度：O(1)
class Solution {
    public int reversePairs(int[] nums) {
        int ret = 0;
        for(int i = 0; i < nums.length; i++) {
            for(int j = i+1; j < nums.length; j++) {
                if(nums[i] / 2.0 > nums[j]) ret++;
            }
        }
        return ret;
    }
}