面试题51：数组中的逆序对
题目要求：
如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组，求出这个数组中的逆序对总数。例如输入{7,5,6,4}，一共有5个逆序对，分别是（7,6），（7,5），（7,4），（6,4），（5,4）。
解题思路：
思路1：暴力解决。顺序扫描数组，对于每个元素，与它后面的数字进行比较，因此这种思路的时间复杂度为o(n^2)。
思路2：
上述思路在进行比较后，并没有将相关信息留下，其实在比较之后可以进行局部的排序，从而降低比较的次数，降低时间复杂度。
可通过如下步骤求逆序对个数：先把数组逐步分隔成长度为1的子数组，统计出子数组内部的逆序对个数，然后再将相邻两个子数组合并成一个有序数组并统计数组之间的逆序对数目，直至合并成一个大的数组。其实，这是二路归并的步骤，只不过在归并的同事要多进行一步统计。因此时间复杂度o(nlogn)，空间复杂度o(n)，如果使用原地归并排序，可以将空间复杂度降为o(1)。
本文使用经典二路归并排序实现。以{7,5,6,4}为例，过程如下：
[7 5 6 4]
/ \ 分：将长度为4的数组分成长度为2的数组
[7 5] [6 4]
/ \ / \ 分：将长度为2的数组分成长度为1的数组
[7] [5] [6] [4]
\ / \ / 和：1->2，并记录子数组内的逆序对
[5 7] [4 6]
\ / 和：2->4，并记录子数组内的逆序对
[4 5 6 7]
代码实现
package chapter5;
/**
* Created with IntelliJ IDEA
* Author: ryder
* Date : 2017/8/14
* Time : 19:36
* Description:数组中的逆序对
**/
public class P249_InversePairs {
public static int inversePairs(int[] data){
if(data==null || data.length<2)
return 0;
return mergeSortCore(data, 0, data.length - 1);
}
public static int mergeSortCore(int[] data,int start,int end){
if(start>=end)
return 0;
int mid = start+(end-start)/2;
int left = mergeSortCore(data,start,mid);
int right = mergeSortCore(data,mid+1,end);
int count = mergerSortMerge(data,start,mid,end);
return left+right+count;
}
//start~mid, mid+1~end
public static int mergerSortMerge(int[] data,int start,int mid,int end){
int[] temp = new int[end-start+1];
for(int i=0;i<=end-start;i++)
temp[i] = data[i+start];
int left = 0,right = mid+1-start,index = start,count = 0;
while (left<=mid-start && right<=end-start){
if(temp[left]<=temp[right])
data[index++] = temp[left++];
else{
data[index++] = temp[right++];
count += (mid-start)-left+1;
}
}
while (left<=mid-start)
data[index++] = temp[left++];
while (right<=end-start)
data[index++] = temp[right++];
return count;
}
public static void main(String[] args){
System.out.println(inversePairs(new int[]{7,5,6,4}));
System.out.println(inversePairs(new int[]{5,6,7,8,1,2,3,4}));
}
}
运行结果
5
16
网友评论