2.＜tag-排序和归并排序巧妙解题＞-剑指 Offer 51. 数组中的逆序对 + lt. 315. 计算右侧小于当前元素的个数 + 补充题-计算数组的小和 1_tag 匹配度 排序

剑指 Offer 51. 数组中的逆序对

[案例需求]

[思路分析一, 归并排序法解题]

• 这道题充分利用了归并排序的性质
• 视频题解

还有以下解法等待补充:

1. 有序数组 （Sorted List）
2. 归并排序 （Merge Sort）
3. 树状数组 （Binary Indexed Tree）
4. 线段树 （Segment Tree）

[代码实现]

class Solution {
    //利用归并排序解答，在合并的时候，当左边的大于右边，就计算逆序数。
    //计算公式； mid-left+1
    //定义一个全局的计数器变量
    int count = 0;
    public int reversePairs(int[] nums) {
        this.count = 0;
        mergeSort(nums, 0, nums.length-1);
        return count;
    }
    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);
        //合并
        merge(nums,left,mid,right);
    }
    public void merge(int[] nums,int left,int mid,int right){
        //定义一个临时数组
        int[] temp = new int[right-left+1];
        //定义一个指针，指向第一个数组的第一个元素
        int i = left;
        //定义一个指针，指向第二个数组的第一个元素
        int j = mid+1;
        //定义一个指针，指向临时数组的第一个元素
        int t = 0;
        //当两个数组都有元素的时候，遍历比较每个元素大小
        while(i <= mid && j <= right){
            //比较两个数组的元素，取较小的元素加入到，临时数组中
            //并将两个指针指向下一个元素
            if(nums[i] <= nums[j]){
                temp[t++] = nums[i++];
            }else{
                //当左边数组的大与右边数组的元素时，就对当前元素以及后面的元素的个数进行统计，
                //此时这个数就是，逆序数
                //定义一个计数器，记下每次合并中存在的逆序数。

                // mid 前有多少个 temp[j] 比当前 temp[i] 小 
                //mid前，有多少个temp[i]比当前的temp[j]大，temp[j]是固定的，因为是从小到大排序归并的，所有之后的temp[i]都比当前的大。
                count += mid-i+1;
                temp[t++] = nums[j++];
            }
        }
        //当左边的数组没有遍历完成后，直接将剩余元素加入到临时数组中
        while(i <= mid){
            temp[t++] = nums[i++];
        }
        //当右边的数组没有遍历完成后，直接将剩余元素加入到临时数组中
        while(j <= right){
            temp[t++] =nums[j++];
        }
        //将新数组中的元素，覆盖nums旧数组中的元素。
        //此时数组的元素已经是有序的
        for(int k =0; k< temp.length;k++){
            nums[left+k] = temp[k];
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64

lt. 315. 计算右侧小于当前元素的个数

[案例需求]

[思路分析]

[代码实现]

1

补充题-计算数组的小和

[案例需求]

[思路分析]

归并排序的应用，当归并过程中发现左边的数小于右边的数，即得到一组小和。如1 3 5 7 和 2 4 6 8，当左边遍历第一个数，有1 < 2，则1也小于2右边的所有数，即这组小和为1*4。

• 整个数组的小和=数组左半部分贡献的小和+数组右半部分贡献的小和+左右两部分之间贡献的小和

参考文章:

1. https://mp.weixin.qq.com/s/rMsbcUf9ZPhvfRoyZGW6HA
2. 点我

[代码实现, 核心代码模式]

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param nums int整型ArrayList 
     * @return long长整型
     */
    public long calArray (ArrayList<Integer> nums) {
        // write code here
        int len = nums.size();
        int[] arr = new int[len];
        int index = 0;
        
        for(int x : nums){
            arr[index++] = x; 
        }
        
        return merge(arr, 0, len - 1);
    }
    
    public long merge(int[] nums, int left, int right){
        if(left >= right)return 0;
        
        int mid = left + ((right - left) >> 1);
        long leftSum = merge(nums, left, mid);
        long rightSum = merge(nums, mid + 1, right);
        
        long curSum = getSmallSum(nums, left, mid, right);
        
        return leftSum + rightSum + curSum;
    }
    
    public long getSmallSum(int[] nums, int left, int mid, int right){
        int L = left;
        int R = mid + 1;
        
        int[] temp = new int[right - left + 1];
        int index = 0;
        long tempSum = 0;
        
        while(L <= mid && R <= right){
            if(nums[L] <= nums[R]){
                 tempSum += nums[L] * (right - R + 1);
                temp[index++] = nums[L++];
               
            }else{
                temp[index++] = nums[R++];
            }
        }
        
        while(L <= mid)temp[index++] = nums[L++];
        while(R <= right)temp[index++] = nums[R++];
        
        for(int i = 0; i < index; i++){
            nums[i + left] = temp[i];
        }
        
        return tempSum;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64

[代码实现, ACM模式]

import java.util.Scanner;
public class Main {

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int len = in.nextInt();
        int[] nums = new int[len];
        for (int i = 0; i < len; i++) {
            nums[i] = in.nextInt();
        }

        System.out.println(mergeSort(nums, 0, nums.length - 1, new int[nums.length]));
    }

    public static long mergeSort(int[] nums, int left, int right, int[] temp) {
        if (left >= right) {
            return 0;
        }

        int mid = left + (right - left) / 2;
        //
        long leftTempSum = mergeSort(nums, left, mid, temp);
        long rightTempSum = mergeSort(nums, mid + 1, right, temp);
        long curTempSum = merge(nums, left, mid, right, temp);

        return leftTempSum + rightTempSum + curTempSum;
    }

    // 合并 nums[left:mid] nums[mid + 1:right] 这两段有序数组
    public static long merge(int[] nums, int left, int mid, int right, int[] temp) {
        int i = left, j = mid + 1, t = 0;
        long tempSum = 0;

        while (i <= mid && j <= right) {
            if (nums[i] <= nums[j]) {
                // 由于左右子数组均有序，所以 nums[i] 比 nums[j:right] 这些元素都要小，所以 nums[i] “产生” 的小和为 nums[i] * (right - j + 1)
                tempSum += nums[i] * (right - j + 1);
                temp[t++] = nums[i++];
            } else {
                temp[t++] = nums[j++];
            }
        }

        while (i <= mid) {
            temp[t++] = nums[i++];
        }

        while (j <= right) {
            temp[t++] = nums[j++];
        }

        t = 0;//temp ***有 right - left + 1 个元素
        while (left <= right) {
            nums[left++] = temp[t++];
        }

        return tempSum;
    }

}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60

===

import java.util.*;
public class Main{
    public static int[] tmp=new int[100000];
    public static void main(String[] args){
        Scanner sc=new Scanner(System.in);
        int N=sc.nextInt();
        int[] arr=new int[N];
        for(int i=0;i<N;i++){
            arr[i]=sc.nextInt();
        }
        
        long count=getMinSum(arr,0,N-1);
        System.out.println(count);
    }
    
    public static long merge(int[] arr,int left,int mid,int right){
        int len=arr.length;
        
        int i=left,j=mid+1;
        int k=0;
        long res=0;
        
        while(i<=mid && j<=right){
            if(arr[i]<=arr[j]){
                res += (right-j+1)*arr[i];
                tmp[k++]=arr[i++];
            }else{
                tmp[k++]=arr[j++];
            }
        }
        while(i<=mid) tmp[k++]=arr[i++];
        while(j<=right) tmp[k++]=arr[j++];
        
        for(i=left,k=0;i<=right;i++){
            arr[i]=tmp[k++];
        }
        return res;
    }
    
    public static long getMinSum(int[] arr,int left,int right){
        if(left==right) return 0;
        int mid=(left+right)/2;
        long lSum=getMinSum(arr,left,mid);
        long rSum=getMinSum(arr,mid+1,right);
        if(arr[mid]<=arr[mid+1]){
            long tmpSum=0;
            for(int i=left;i<=mid;i++){
                tmpSum += arr[i];
            }
            return lSum+rSum+tmpSum*(right-mid);
        }
        long crossSum=merge(arr,left,mid,right);
        
        return lSum+rSum+crossSum;
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57