每天一道剑指offer-数组中的逆序对
数组中的逆序对
题目描述
在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组,求出这个数组中的逆序对的总数P。并将P对1000000007取模的结果输出。 即输出P%1000000007
public int InversePairs(int [] arr) { if(arr == null || arr.length <= 1){ return 0; } return mergeSort(arr, 0, arr.length - 1).pairs;}输入描述
- 题目保证输入的数组中没有相同的数字
- 数据范围：对于%50的数据,size<=10^4；对于%75的数据,size<=10^5；对于%100的数据,size<=2*10^5
解析
借助归并排序的流程，将归并流程中前一个数组的数比后一个数组的数小的情况记录下来。
归并的原始逻辑是根据输入的无序数组返回一个新建的排好序的数组：
public int[] mergeSort(int[] arr, int start, int end){ if(arr == null || arr.length == 0 || start < 0 || end > arr.length - 1 || start > end){ throw new IllegalArgumentException(); } if(start == end){ return new int[]{ arr[end] }; }
int[] arr1 = mergeSort(arr, start, mid); int[] arr2 = Info right = mergeSort(arr, mid + 1, end); int[] copy = new int[arr1.length + arr2.length]; int p1 = 0, p2 = 0, p = 0;
while(p1 < arr1.length && p2 < arr2.length){ if(arr1[p1] > arr2[p2]){ copy[p++] = arr1[p1++]; }else{ copy[p++] = arr2[p2++]; } } while(p1 < arr1.length){ copy[p++] = arr1[p1++]; } while(p2 < arr2.length){ copy[p++] = arr2[p2++]; } return copy;}而我们需要再此基础上对子状态收集的信息进行改造，假设左右两半部分分别有序了，那么进行 merge的时候，不应是从前往后复制了，这样当 arr1[p1]>arr2[p2]的时候并不知道 arr2的 p2后面还有多少元素是比 arr1[p1]小的，要想一次比较就统计出 arr2中所有比 arr1[p1]小的数需要将 p1,p2从 arr1,arr2的尾往前遍历：
而将比较后较大的数移入辅助数组的逻辑还是一样。这样当前递归状态需要收集左半子数组和右半子数组的变成有序过程中记录的逆序对数和自己 merge记录的逆序对数之和就是当前状态要返回的信息，并且 merge后形成的有序辅助数组也要返回。
public int InversePairs(int [] arr) { if(arr == null || arr.length <= 1){ return 0; } return mergeSort(arr, 0, arr.length - 1).pairs;}
class Info{ int arr[]; int pairs; Info(int[] arr, int pairs){ this.arr = arr; this.pairs = pairs; }}
public Info mergeSort(int[] arr, int start, int end){ if(arr == null || arr.length == 0 || start < 0 || end > arr.length - 1 || start > end){ throw new IllegalArgumentException(); } if(start == end){ return new Info(new int[]{arr[end]}, 0); }
int pairs = 0; int mid = start + ((end - start) >> 1); Info left = mergeSort(arr, start, mid); Info right = mergeSort(arr, mid + 1, end); pairs += (left.pairs + right.pairs) % 1000000007;
int[] arr1 = left.arr, arr2 = right.arr, copy = new int[arr1.length + arr2.length]; int p1 = arr1.length - 1, p2 = arr2.length - 1, p = copy.length - 1;
while(p1 >= 0 && p2 >= 0){ if(arr1[p1] > arr2[p2]){ pairs += (p2 + 1); pairs %= 1000000007; copy[p--] = arr1[p1--]; }else{ copy[p--] = arr2[p2--]; } }
while(p1 >= 0){ copy[p--] = arr1[p1--]; } while(p2 >= 0){ copy[p--] = arr2[p2--]; }
return new Info(copy, pairs % 1000000007);}出自：http://www.zhenganwen.top
已获授权
END
本文参与 腾讯云自媒体分享计划，分享自微信公众号。
原始发表：2019-02-18，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录