题目描述
在数组中的两个数字,如果前面一个数字大于后面的数字,则这两个数字组成一个逆序对。输入一个数组,求出这个数组中的逆序对的总数。
要找到数组中的逆序对,一种思路是每遍历到一个元素的时候就和后面的元素进行一一比较,这种算法的时间复杂度是O(n2),所以不是很理想。我们可以借鉴归并排序的思想,把数组划分为子数组,然后对每个子数组中的逆序对数进行统计,统计完成后再并到一个新的数组中进行统计,这样就化整为零,实现了高效统计。总计起来思路就是:首先把数组划分为子数组,然后统计子数组中的逆序对数,然后继续统计相邻子数组的逆序对数,在统计相邻子数组中的逆序对数的时候,需要使用两个指针,一个指向第一个数组的尾部,一个指向第二个数组的尾部,如果第一个指针指向的元素大于后面的,说明相邻之间存在逆序对,并把较大的那个数拷贝到一个临时数组中,然后指针往前移动,直到所有的子数组以及相邻的子数组的逆序对数统计完毕。
下面是这种思路的实现代码(已被牛客AC):
package com.rhwayfun.offer;
public class InversePairsCount {
public int InversePairs(int[] array) {
if (array == null || array.length <= 0)
return 0;
int[] copy = new int[array.length];
for (int i = 0; i < array.length; i++)
copy[i] = array[i];
int count = mergeCount(array, copy, 0, array.length - 1);
return count;
}
private int mergeCount(int[] array, int[] copy, int start, int end) {
if(start == end){
copy[start] = array[start];
return 0;
}
int len = (end - start) / 2;
int leftCount = mergeCount(copy, array, start, start + len);
int rightCount = mergeCount(copy, array, start + len + 1, end);
//i指向第一个子数组的最后一个下标
int i = start +len;
//j指向第二个子数组的最后一个下标
int j = end;
int indexCopy = end;
int count = 0;
while(i >= start && j >= start + len + 1){
if(array[i] > array[j]){
copy[indexCopy--] = array[i--];
count += j - start - len;
}else{
copy[indexCopy--] = array[j--];
}
}
for(; i >= start; i--)
copy[indexCopy--] = array[i];
for(; j >= start + len + 1; j--)
copy[indexCopy--] = array[j];
return leftCount + rightCount + count;
}
public static void main(String[] args) {
int[] array = new int[]{7,5,6,4};
int count = new InversePairsCount().InversePairs(array);
System.out.println(count);
}
}
时间: 2024-09-01 07:00:58