算法问题——归并排序的思想

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

/**
 * Copyright (C), 2018-2020
 * FileName: 逆序数对
 * Author:   xjl
 * Date:     2020/8/31 13:09
 * Description:
 */
package Test_Pricate;

import org.junit.Test;

public class 逆序数对 {

    /**
     * 如果是在有序的数字的情况下
     *
     * @param nums1
     * @param nums2
     * @return
     */
    public int reversePairs2(int[] nums1, int[] nums2) {
        int[] array = new int[nums1.length + nums2.length];
        int i = 0;
        int j = 0;
        //统计结果
        int count = 0;

        for (int k = 0; k < array.length; k++) {
            if (i > nums1.length - 1) {
                array[k] = nums2[j++];
            } else if (j > nums2.length - 1) {
                array[k] = nums2[i++];
            } else if (nums1[i] > nums2[j]) {
                array[i] = nums2[j++];
                count += nums1.length - i;
            } else {
                array[i] = nums1[i++];
            }
        }
        return count;
    }

    @Test
    public void test1() {
        int[] nums1 = {1, 2, 4};
        int[] nums2 = {3, 5, 6};
        int i = reversePairs2(nums1, nums2);
        System.out.println(i);
    }

    /**
     * 暴力的方法 时间超时的
     *
     * @param nums
     * @return
     */
    public int reversePairs(int[] nums) {
        int count = 0;
        for (int i = 0; i < nums.length; i++) {
            for (int j = i + 1; j < nums.length; j++) {
                if (nums[i] > nums[j]) {
                    count++;
                }
            }
        }
        return count;
    }

    @Test
    public void test() {
        int[] nums = {1, 2, 4, 3, 5, 6};
        int ans = reversePairs1(nums);
        System.out.println(ans);
    }

    public int reversePairs1(int[] nums) {
        int len = nums.length;
        if (len < 2) {
            return 0;
        }
        int[] copy = new int[len];
        for (int i = 0; i < len; i++) {
            copy[i] = nums[i];
        }
        int[] temp = new int[len];
        return reversePairs(copy, 0, len - 1, temp);
    }

    /**
     * nums[left..right] 计算逆序对个数并且排序
     *
     * @param nums
     * @param left
     * @param right
     * @param temp
     * @return
     */
    private int reversePairs(int[] nums, int left, int right, int[] temp) {
        if (left == right) {
            return 0;
        }

        int mid = left + (right - left) / 2;
        int leftPairs = reversePairs(nums, left, mid, temp);
        int rightPairs = reversePairs(nums, mid + 1, right, temp);

        if (nums[mid]