算法-逆序对（归并思路）

2022-3-30 diaba 算法 



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);
    }
}

« 算法-选择法排序 | 算法-小和问题（归并思路，O(N*logN)）»

发表评论：

Powered by emlog 京ICP备15045175号-1 Copyright © 2022