lintcode 逆序对(Reverse Pairs )(Java)

题目

在数组中的两个数字如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。给你一个数组，求出这个数组中逆序对的总数。 概括：如果a[i] > a[j] 且 i < j， a[i] 和 a[j] 构成一个逆序对。

样例

序列 [2, 4, 1, 3, 5] 中，有 3 个逆序对 (2, 1), (4, 1), (4, 3)，则返回 3 。

分析

解法一：考虑暴力解法，两个for循环直接获得结果，当然这样并不是高效的，时间复杂度为O(n^2); 解法二：用归并解法，时间复杂度为O(nlogn),空间复杂度为O(n)，可以参考 lintcode 整数排序 II | 归并排序（Java）

代码

//解法一 public long reversePairs(int[] A) { // Write your code here int num = 0; for (int i = 0; i < A.length - 1; i++){ for (int j = i; j < A.length; j++){ if (A[i] > A[j]) num++; } } return num; } //解法二 public class Solution { /** * @param A an array * @return total of reverse pairs */ private static int[] aux; int num = 0; public long reversePairs(int[] A) { // Write your code here aux = new int[A.length]; sort(A,0,A.length-1); return num; } private void sort(int[] a, int lo, int hi) { if (hi<=lo) return; int mid = lo + (hi - lo)/2; //递归 sort(a, lo, mid);//左半边排序 sort(a, mid+1, hi);//右半边排序 merge(a,lo,mid,hi);//归并结果 } //归并算法 private void merge(int[] a, int lo, int mid, int hi){ int i = lo; int j = mid + 1; for(int k = lo; k <= hi; k++){ aux[k] = a[k]; } //每次k,i或j都会右移一个 for (int k = lo; k <= hi; k++){ if (i>mid) a[k] = aux[j++];//如果左边归并完，则只添加右边 else if (j>hi) { a[k] = aux[i++];//如果右边归并完，则只添加左边 } //如果右边的小于左边的，则添加右边的 else if (aux[j] < aux[i]) { a[k] = aux[j++]; //右边的小于左边的当前数，则他小于当前至mid的所有数，因为数组在合并时已经为有序的了。 num+=mid-i+1; } else a[k] = aux[i++];//如果左边的小于右边的，则添加左边的 } } }

题目地址：http://www.lintcode.com/zh-cn/problem/reverse-pairs/