package com.jiucaiyuan.net.question;



/**

 * <pre>

 * 一个数组arr中，如果左边的数，比右边的数大，则这两个数组成一个逆序对（不一定相邻），找出数组中所有逆序对

 *   采用归并排序的思路进行改进实现

 *   时间复杂度O(N*logN)

 * </pre>

 *

 * @Author jiucaiyuan  2022/3/30 23:01

 * @mail services@jiucaiyuan.net

 */



public class FindReversePair {



    public static void reversePair(int[] arr) {

        if (arr == null || arr.length < 2) {

            return;

        }

        process(arr, 0, arr.length - 1);

    }



    /**

     * @param arr

     * @param l

     * @param r

     * @return

     */

    public static void process(int[] arr, int l, int r) {

        if (l == r) {

            return;

        }

        int mid = l + ((r - l) >> 1);

        process(arr, l, mid);

        process(arr, mid + 1, r);

        merge(arr, l, mid, r);

    }



    /*

     * 合并arr[l,mid] 和 arr[mid+1,r] 两个数组

     */

    private static void merge(int[] arr, int l, int mid, int r) {

//        System.out.println("合并 "+print(arr,l,mid)+"   "+print(arr,mid+1,r));

        //合并后的数组

        int[] temp = new int[r - l + 1];

        int i = 0;

        int p1 = l;

        int p2 = mid + 1;

        //两个数组都有数时

        while (p1 <= mid && p2 <= r) {

            //先拷贝大的数字，再拷贝小的

            if (arr[p1] <= arr[p2]) {

                temp[i++] = arr[p2++];

            } else {

                System.out.println(arr[p1]+">"+arr[p2]);

                temp[i++] = arr[p1++];

            }

        }

        //前半段数组长

        while (p1 <= mid) {

            temp[i++] = arr[p1++];

        }

        //后半段数组长

        while (p2 <= r) {

            temp[i++] = arr[p2++];

        }

        //把合并后的temp数组复制到arr中

        for (int index = 0; index < temp.length; index++) {

            arr[l + index] = temp[index];

        }

    }

    public static void main(String[] args) {

        int[] arr = {3, 4, 2, 5, 1};

        System.out.println(print(arr,0,arr.length-1));

        reversePair(arr);

    }

    private static String print(int[] arr, int l, int mid) {

        StringBuffer sb = new StringBuffer();

        for(int i=l;i<=mid;i++){

            sb.append(arr[i]).append(",");

        }

        return sb.substring(0,sb.length()-1);

    }

}