本文共 2351 字，大约阅读时间需要 7 分钟。

在解决该问题之前，先来看一下归并排序。

// 归并排序	public static void mergeSort(int[] arr) {
   		if(arr==null || arr.length<2) {
   			return;		}		sortProcess(arr,0,arr.length-1);	}		public static void sortProcess(int[] arr,int L,int R) {
   		if(L==R) {
   			return;		}		int mid = L + ((R-L) >> 1);		sortProcess(arr, L, mid);		sortProcess(arr, mid+1, R);		merge(arr,L,mid,R);	}	public static void merge(int[] arr,int L,int mid,int R) {
   		int[] temp = new int[R-L+1];		int i = 0;		int p1 = L;		int p2 = mid + 1;		while(p1<=mid&&p2<=R) {
   			temp[i++] = arr[p1]

此题 与小数和问题类似

小和问题

在一个数组中，每一个数左边比当前数小的数累加起来，叫做这个数组的小和。求一个数组

的小和。

例子：

[1,3,4,2,5]

1左边比1小的数，没有；

3左边比3小的数，1；

4左边比4小的数，1、3；

2左边比2小的数，1；

5左边比5小的数，1、3、4、2；

所以小和为1+1+3+1+1+3+4+2=16

public static int smallSum(int[] arr) {
   		if(arr==null||arr.length<2) {
   			return 0;		}		return mergeSort_2(arr,0,arr.length-1);	}		public static int mergeSort_2(int[] arr,int L,int R) {
   		// 终止条件		if(L==R) {
   			return 0;		}		int mid = L + ((R-L)>>1);		return mergeSort_2(arr,L,mid) + mergeSort_2(arr,mid+1,R)+merge_2(arr,L,mid,R);	}	public static int merge_2(int[] arr,int L,int mid,int R) {
   		int[] temp = new int[R-L+1];		int i = 0;		int p1 = L;		int p2 = mid+1;		int res = 0;		while(p1<=mid&&p2<=R) {
   			res += arr[p1]

而本题在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组，求出这个数组中的逆序对的总数。

package com.lcz.leetcode;/** * 数组中的逆序对 * @author LvChaoZhang * */public class Leetcode_offer51 {
   	class Solution{
   		public int reversePairs(int[] nums) {
   			if(nums==null||nums.length<2) {
   				return 0;			}			return mergeSort(nums,0,nums.length-1);		}				public  int mergeSort(int[] nums,int L,int R) {
   			// 终止条件			if(L==R) {
   				return 0;			}			int mid = L + ((R-L)>>1);			int leftPairs = mergeSort(nums, L, mid);			int rightPairs = mergeSort(nums, mid+1, R);			if(nums[mid]<=nums[mid+1]) {
   				return leftPairs+rightPairs;			}			int crossPairs = merge(nums,L,mid,R);			return leftPairs+rightPairs+crossPairs;		}				public  int merge(int[] arr,int L,int mid,int R) {
   			int[] temp = new int[R-L+1];			int res = 0;			int i = 0;			int p1 = L;			int p2 = mid+1;			while(p1<=mid&&p2<=R) {
   				res += arr[p1]>arr[p2]?(mid-p1+1):0;				temp[i++] = arr[p1]<=arr[p2]?arr[p1++]:arr[p2++];			}			while(p1<=mid) {
   				temp[i++] = arr[p1++];			}			while(p2<=R) {
   				temp[i++] = arr[p2++];			}			for(i=0;i

转载地址：http://tzwdf.baihongyu.com/