归并排序

1）整体是递归，左边排好序+右边排好序+merge让整体有序

2）让其整体有序的过程里用了排外序方法

3）利用master公式来求解时间复杂度

4）当然可以用非递归实现

归并排序复杂度

T(N) = 2*T(N/2) + O(N^1)

根据master可知时间复杂度为O(N*logN)

merge过程需要辅助数组，所以额外空间复杂度为O(N)

归并排序的实质是把比较行为变成了有序信息并传递，比O(N^2)的排序快

代码实现

package com.lzf2.class03;

/**
 * 归并排序
 */
public class MergeSort {
    //1.递归版本
    public static void sort(int[] arr){
        if(arr == null || arr.length ==0){
            return;
        }
        process(arr,0,arr.length-1);
    }
    //请把 L -- R位置排序
    private static void process(int[] arr,int L,int R){
        //base case
        if(L == R){
            return;
        }
        int mid = L +((R - L) >> 1);
        //左边排序
        process(arr,L,mid);
        //右边排序
        process(arr,mid + 1,R);
        //合并
        merge(arr,L,mid,R);
    }
    private static void merge(int[] arr,int L,int mid,int R){
        int[] help = new int[R - L + 1];
        int i = 0;
        int left = L;
        int right = mid + 1;
        while (left <= mid && right<= R){
            help[i++] = arr[left] < arr[right]?arr[left++]:arr[right++];
        }
        while (left <= mid){
            help[i++] = arr[left++];
        }
        while (right <= R){
            help[i++] = arr[right++];
        }
        //复制到原数组
        for (int j = 0; j < help.length; j++) {
            arr[L + j] = help[j];
        }
    }



    //2.非递归版本
    public static void sort2(int[] arr) {
        if (arr == null || arr.length < 2) {
            return;
        }
        int N = arr.length;
        //步长
        int mergeSize = 1;
        while (mergeSize < N) {

            //当前左组的，第一个位置
            int L = 0;
            while (L < N) {//每轮步长要做的事
                int M = L + mergeSize - 1;//左组最后一个数
                if (M >= N) {//只有左组数，没有右组数，不用继续做了
                    break;
                }
                int R = Math.min(M + mergeSize, N - 1);//右组的最后一个数
                merge(arr, L, M, R);
                L = R + 1;//去搞下一个左组
            }
            //防止溢出
            if (mergeSize > N / 2) {
                break;
            }

            //步长乘2
            mergeSize <<= 1;
        }
    }
    // for test
    public static int[] generateRandomArray(int maxSize, int maxValue) {
        int[] arr = new int[(int) ((maxSize + 1) * Math.random())];
        for (int i = 0; i < arr.length; i++) {
            arr[i] = (int) ((maxValue + 1) * Math.random()) - (int) (maxValue * Math.random());
        }
        return arr;
    }

    // for test
    public static int[] copyArray(int[] arr) {
        if (arr == null) {
            return null;
        }
        int[] res = new int[arr.length];
        for (int i = 0; i < arr.length; i++) {
            res[i] = arr[i];
        }
        return res;
    }

    // for test
    public static boolean isEqual(int[] arr1, int[] arr2) {
        if ((arr1 == null && arr2 != null) || (arr1 != null && arr2 == null)) {
            return false;
        }
        if (arr1 == null && arr2 == null) {
            return true;
        }
        if (arr1.length != arr2.length) {
            return false;
        }
        for (int i = 0; i < arr1.length; i++) {
            if (arr1[i] != arr2[i]) {
                return false;
            }
        }
        return true;
    }

    // for test
    public static void printArray(int[] arr) {
        if (arr == null) {
            return;
        }
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i] + " ");
        }
        System.out.println();
    }

    // for test
    public static void main(String[] args) {
        int testTime = 100000;
        int maxSize = 100;
        int maxValue = 100;
        System.out.println("测试开始");
        for (int i = 0; i < testTime; i++) {
            int[] arr1 = generateRandomArray(maxSize, maxValue);
            int[] arr2 = copyArray(arr1);
            sort(arr1);
            sort2(arr2);
            if (!isEqual(arr1, arr2)) {
                System.out.println("出错了！");
                printArray(arr1);
                printArray(arr2);
                break;
            }
        }
        System.out.println("测试结束");
    }
}

第一题

在一个数组中，一个数左边比它小的数的总和，叫数的小和，所有数的小和累加起来，叫数组小和。求数组小和。

例子： [1,3,4,2,5]

1左边比1小的数：没有

3左边比3小的数：1

4左边比4小的数：1、3

2左边比2小的数：1

5左边比5小的数：1、3、4、 2

所以数组的小和为1+1+3+1+1+3+4+2=16

(即：求每个数右边右多少个数比它大)

代码实现

package com.lzf2.class03;

/**
 * 小和问题  (即：求每个数右边右多少个数比它大)
 */
public class SmallSum {

    public static int getSamllSum(int[] arr){
        if(arr == null || arr.length < 2){
            return 0;
        }
        return process(arr,0,arr.length - 1);
    }

    //递归过程
    private static int process(int[] arr,int L,int R){
        //base case
        if(L == R){
            return 0;
        }
        int mid = L + ((R - L) >> 1);
        return process(arr,L,mid) + process(arr,mid + 1,R) +merge(arr,L,mid,R);
    }

    private static int merge(int[] arr,int L ,int M , int R){
        int[] help = new int[R - L + 1];
        int i =0;
        int res = 0;
        //拷贝右边不产生小和，相等时拷贝右边。
        int p1 = L;
        int p2 = M + 1;
        //两个都不越界时
        while (p1 <= M && p2<= R){
            //是否产生小和
            res += arr[p1] < arr[p2] ? (R - p2 + 1) * arr[p1]:0;
            //拷贝过程，相等考右边
            help[i++] = arr[p1] < arr[p2] ? arr[p1++] : arr[p2++];
        }
        while (p1 <= M){
            help[i++] = arr[p1++];
        }
        while (p2 <= R){
            help[i++] = arr[p2++];
        }
        //数组复制
        for (int j = 0; j < help.length; j++) {
            arr[L + j] = help[j];
        }

        return res;
    }
    // for test
    public static int comparator(int[] arr) {
        if (arr == null || arr.length < 2) {
            return 0;
        }
        int res = 0;
        for (int i = 1; i < arr.length; i++) {
            for (int j = 0; j < i; j++) {
                res += arr[j] < arr[i] ? arr[j] : 0;
            }
        }
        return res;
    }

    // for test
    public static int[] generateRandomArray(int maxSize, int maxValue) {
        int[] arr = new int[(int) ((maxSize + 1) * Math.random())];
        for (int i = 0; i < arr.length; i++) {
            arr[i] = (int) ((maxValue + 1) * Math.random()) - (int) (maxValue * Math.random());
        }
        return arr;
    }

    // for test
    public static int[] copyArray(int[] arr) {
        if (arr == null) {
            return null;
        }
        int[] res = new int[arr.length];
        for (int i = 0; i < arr.length; i++) {
            res[i] = arr[i];
        }
        return res;
    }

    // for test
    public static boolean isEqual(int[] arr1, int[] arr2) {
        if ((arr1 == null && arr2 != null) || (arr1 != null && arr2 == null)) {
            return false;
        }
        if (arr1 == null && arr2 == null) {
            return true;
        }
        if (arr1.length != arr2.length) {
            return false;
        }
        for (int i = 0; i < arr1.length; i++) {
            if (arr1[i] != arr2[i]) {
                return false;
            }
        }
        return true;
    }

    // for test
    public static void printArray(int[] arr) {
        if (arr == null) {
            return;
        }
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i] + " ");
        }
        System.out.println();
    }

    // for test
    public static void main(String[] args) {
        int testTime = 500000;
        int maxSize = 100;
        int maxValue = 100;
        boolean succeed = true;
        for (int i = 0; i < testTime; i++) {
            int[] arr1 = generateRandomArray(maxSize, maxValue);
            int[] arr2 = copyArray(arr1);
            if (getSamllSum(arr1) != comparator(arr2)) {
                succeed = false;
                printArray(arr1);
                printArray(arr2);
                break;
            }
        }
        System.out.println(succeed ? "Nice!" : "Fucking fucked!");
    }
}

第二题

求有多少逆序对(即：求每个数右边有多少个数比它小）

[3,1,0,4,3,1]

逆序对：3,1 3,0 3,1
1,0
4,3 4,1
3,1

代码实现

package com.lzf2.class03;

/**
 * 逆序对问题 (即：求每个数右边有多少个数比它小）
 */
public class ReverPairNumber {

    public static int getReverNumber(int[] arr) {
        if (arr == null || arr.length < 2) {
            return 0;
        }
        return process(arr, 0, arr.length - 1);
    }

    //递归过程
    private static int process(int[] arr, int L, int R) {
        //base case
        if (L == R) {
            return 0;
        }
        //mid
        int mid = L + ((R - L) >> 1);
        //左边求逆序对
        int leftNum = process(arr, L, mid);
        //右边求逆序对
        int rightNum = process(arr, mid + 1, R);
        //合并
        return leftNum + rightNum + merge(arr, L, mid, R);
    }

    private static int merge(int[] arr, int L, int M, int R) {
        int[] help = new int[R - L + 1];
        int i = help.length - 1;
        int p1 = M;
        int p2 = R;
        int res = 0;
        while (p1 >= L && p2 > M) {
            res += arr[p1] > arr[p2] ? (p2 - M) : 0;
            help[i--] = arr[p1] > arr[p2] ? arr[p1--] : arr[p2--];
        }
        while (p1 >= L){
            help[i--] = arr[p1--];
        }
        while (p2 > M){
            help[i--] = arr[p2--];
        }
        for (i = 0; i < help.length; i++) {
            arr[L + i] = help[i];
        }
        return res;
    }



    // for test
    public static int comparator(int[] arr) {
        int ans = 0;
        for (int i = 0; i < arr.length; i++) {
            for (int j = i + 1; j < arr.length; j++) {
                if (arr[i] > arr[j]) {
                    ans++;
                }
            }
        }
        return ans;
    }

    // for test
    public static int[] generateRandomArray(int maxSize, int maxValue) {
        int[] arr = new int[(int) ((maxSize + 1) * Math.random())];
        for (int i = 0; i < arr.length; i++) {
            arr[i] = (int) ((maxValue + 1) * Math.random()) - (int) (maxValue * Math.random());
        }
        return arr;
    }

    // for test
    public static int[] copyArray(int[] arr) {
        if (arr == null) {
            return null;
        }
        int[] res = new int[arr.length];
        for (int i = 0; i < arr.length; i++) {
            res[i] = arr[i];
        }
        return res;
    }

    // for test
    public static boolean isEqual(int[] arr1, int[] arr2) {
        if ((arr1 == null && arr2 != null) || (arr1 != null && arr2 == null)) {
            return false;
        }
        if (arr1 == null && arr2 == null) {
            return true;
        }
        if (arr1.length != arr2.length) {
            return false;
        }
        for (int i = 0; i < arr1.length; i++) {
            if (arr1[i] != arr2[i]) {
                return false;
            }
        }
        return true;
    }

    // for test
    public static void printArray(int[] arr) {
        if (arr == null) {
            return;
        }
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i] + " ");
        }
        System.out.println();
    }

    // for test
    public static void main(String[] args) {
        int testTime = 500000;
        int maxSize = 100;
        int maxValue = 100;
        System.out.println("测试开始");
        for (int i = 0; i < testTime; i++) {
            int[] arr1 = generateRandomArray(maxSize, maxValue);
            int[] arr2 = copyArray(arr1);
            if (getReverNumber(arr1) != comparator(arr2)) {
                System.out.println("Oops!");
                printArray(arr1);
                printArray(arr2);
                break;
            }
        }
        System.out.println("测试结束");
    }

}

第三题

在一个数组中，

对于每个数num，求有多少个后面的数 * 2 依然<num，求总个数

比如：[3,1,7,0,2]

3的后面有：1，0

1的后面有：0

7的后面有：0，2

0的后面没有

2的后面没有

所以总共有5个

代码实现

package com.lzf2.class03;

/**
 * num的右边有多少个数*2后仍然<num
 */
public class BiggerThanRightTwice {

    public static int biggerTwice(int[] arr){
        if(arr == null || arr.length < 2){
            return 0;
        }
        return process(arr,0,arr.length - 1);

    }

    //递归过程
    private static int process(int[] arr,int L,int R){
        //base case
        if(L == R){
            return 0;
        }
        //mid
        int mid = L + ((R - L) >> 1);
        //左边求出个数
        int leftNum = process(arr,L,mid);
        int rightNum = process(arr,mid + 1,R);
        return leftNum + rightNum + merge(arr,L,mid,R);
    }

    private static int merge(int[] arr,int L,int M,int R){
        //先求出答案
        int ans = 0;
        int windowR = M + 1;
        for (int i = L; i <= M; i++) {
            while (windowR <= R && arr[i] > (arr[windowR]*2)){
                windowR++;
            }
            ans += windowR - M - 1;
        }

        //merge过程
        int[] help = new int[R - L + 1];
        int i = 0;
        int p1 = L;
        int p2 = M + 1;
        while (p1 <= M && p2 <= R){
            help[i++] = arr[p1] <= arr[p2]?arr[p1++]:arr[p2++];
        }
        while (p1 <= M){
            help[i++] = arr[p1++];
        }
        while (p2 <= R){
            help[i++] = arr[p2++];
        }
        for (i = 0; i < help.length; i++) {
            arr[L + i] = help[i];
        }
        return ans;
    }


    // for test
    public static int comparator(int[] arr) {
        int ans = 0;
        for (int i = 0; i < arr.length; i++) {
            for (int j = i + 1; j < arr.length; j++) {
                if (arr[i] > (arr[j] << 1)) {
                    ans++;
                }
            }
        }
        return ans;
    }

    // for test
    public static int[] generateRandomArray(int maxSize, int maxValue) {
        int[] arr = new int[(int) ((maxSize + 1) * Math.random())];
        for (int i = 0; i < arr.length; i++) {
            arr[i] = (int) ((maxValue + 1) * Math.random()) - (int) ((maxValue + 1) * Math.random());
        }
        return arr;
    }

    // for test
    public static int[] copyArray(int[] arr) {
        if (arr == null) {
            return null;
        }
        int[] res = new int[arr.length];
        for (int i = 0; i < arr.length; i++) {
            res[i] = arr[i];
        }
        return res;
    }

    // for test
    public static boolean isEqual(int[] arr1, int[] arr2) {
        if ((arr1 == null && arr2 != null) || (arr1 != null && arr2 == null)) {
            return false;
        }
        if (arr1 == null && arr2 == null) {
            return true;
        }
        if (arr1.length != arr2.length) {
            return false;
        }
        for (int i = 0; i < arr1.length; i++) {
            if (arr1[i] != arr2[i]) {
                return false;
            }
        }
        return true;
    }

    // for test
    public static void printArray(int[] arr) {
        if (arr == null) {
            return;
        }
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i] + " ");
        }
        System.out.println();
    }

    // for test
    public static void main(String[] args) {
        int testTime = 500000;
        int maxSize = 100;
        int maxValue = 100;
        System.out.println("测试开始");
        for (int i = 0; i < testTime; i++) {
            int[] arr1 = generateRandomArray(maxSize, maxValue);
            int[] arr2 = copyArray(arr1);
            if (biggerTwice(arr1) != comparator(arr2)) {
                System.out.println("Oops!");
                printArray(arr1);
                printArray(arr2);
                break;
            }
        }
        System.out.println("测试结束");
    }
}

第四题【困难】

给定一个数组arr，两个整数lower和upper。

返回arr中有多少个子数组的累加和在[lower,upper]范围上。

327. 区间和的个数 - 力扣（LeetCode） (leetcode-cn.com)

暴力破解：O(n³) 暴力+使用前缀和：O(n²)

前置知识：前缀和

//求一个数组arr[i~j]位置的和
//每次去遍历i~j位置的数累加起来比较慢
//arr[i~j]的和相当于：arr[0~j] - arr[0~(i-1)]
//可以先准备好一个前缀和数组.想要0~x的累加和时，直接在前缀和数组中拿就可以
int[] arr = {1,2,4,5,6,7};
int[] sum = new int[arr.length];//前缀和数组
sum[0] = arr[0];
for(int i=1;i<arr.length,i++){
    sum[i] = arr[i]+sum[i-1] 
}

问题转换

1.求出以每一个索引位置为结尾的子数组中，有多少个子数组满足条件。
[1,-2,5,6,-6]
所有子数组：
0~0 
1~1 0~1	
2~2	1~2 0~2 
3~3 2~3 1~3 0~3 
4~4 3~4 2~4 1~4 0~4

2.求某个索引位置x为结尾的子数组中有多少子数组满足条件[lower,upper]
即求的是：0~(x-1)各个位置的前缀和在[y-upper,y-lower]上有多少个?(假设x位置的前缀和为y)
		通俗理解：x位置的这个前缀和在他的左边有多少个前缀和满足[y-upper,y-lower]

3.此时忘掉原数组arr，就看前缀和数组preArr.
就是在求：对于前缀和x，它的左组有多少前缀和落在[x-upper,x-lower]上。（用归并就可求得）

代码（归并实现）

package com.lzf2.class03;

/**
 * 给定一个数组arr，两个整数lower和upper。
 * 返回arr中有多少个子数组的累加和在[lower,upper]范围上。
 */
public class CountRangeSum {

    public static int countRangeSum(int[] nums, int lower, int upper) {
        if (nums == null || nums.length == 0) {
            return 0;
        }
        //前缀和数组
        long[] preSum = new long[nums.length];
        preSum[0] = nums[0];
        for (int i = 1; i < preSum.length; i++) {
            preSum[i] = nums[i] + preSum[i - 1];
        }
        return process(preSum, 0, nums.length - 1, lower, upper);
    }

    private static int process(long[] preSum, int L, int R, int lower, int upper) {
        //base case
        if (L == R) {
            return preSum[L] >= lower && preSum[L] <= upper ? 1 : 0;
        }
        //mid
        int mid = L + ((R - L) >> 1);
        int leftCount = process(preSum, L, mid, lower, upper);
        int rightCount = process(preSum, mid + 1, R, lower, upper);
        return leftCount + rightCount + merge(preSum, L, mid, R, lower, upper);
    }

    private static int merge(long[] preSum, int L, int M, int R, int lower, int upper) {
        //求答案
        int ans = 0;
        //对于右组的某个数，左组中有多少数满足 区间条件
        int windowL = L;
        int windowR = L;
        for (int i = M + 1; i <= R; i++) {
            long min = preSum[i] - upper;
            long max = preSum[i] - lower;
            //[L ... R)左闭右开
            while (windowR <= M && preSum[windowR] <= max){
                windowR++;
            }
            while(windowL <= M && preSum[windowL] < min){
                windowL++;
            }
            ans += windowR - windowL;
        }
        //正常merge
        long[] help = new long[R - L + 1];
        int i = 0;
        int p1 = L;
        int p2 = M + 1;
        while (p1 <= M && p2 <= R){
            help[i++] = preSum[p1] <= preSum[p2] ? preSum[p1++] : preSum[p2++];
        }
        while (p1 <= M){
            help[i++] = preSum[p1++];
        }
        while (p2 <= R){
            help[i++] = preSum[p2++];
        }
        for (i = 0; i < help.length; i++) {
            preSum[L + i] = help[i];
        }

        return ans;
    }

}