欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

【剑指Offer】51、数组中的逆序对

程序员文章站 2022-07-10 12:16:46
...

题目

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

思路

        类似于归并排序。

        我们用两个指针分别指向两个子数组的末尾,并每次比较两个指针指向的数字。

        p1指向的数字大于p2指向的数字,存在逆序对。逆序对的数目 = 第二个数组中剩余数字的个数。将p1指向的数字复制到辅助数组,前移p1与p3。

       p1指向的数字小于或者等于p2指向的数字,不存在逆序对。将p2指向的数字复制到辅助数组,前移p2与p3。

测试用例

  1.功能测试(普通数组,递增数组,递减数组,含重复数字)

  2.边界值测试(数组只有两个数字,只有一个数字

  2.特殊测试(null)

代码

public class inversePairs {
	public static 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 = InversePairsCore(array,copy,0,array.length-1);//数值过大求余
		return count;
	}
	
	private static int InversePairsCore(int[] array,int[] copy,int start,int end){
		if(start == end) {
			return 0;
		}
		
		int mid = (start + end) >> 1;
		int leftCount = InversePairsCore(array, copy, start, mid);
		int rightCount = InversePairsCore(array, copy, mid+1, end);
		
		int count = 0;
		int p1 = mid;
		int p2 = end;
		int indexCopy = end;
		
		while(p1 >= start && p2 >= mid+1) {
			if(array[p1] > array[p2]) {
				copy[indexCopy--] = array[p1--];
				count += p2-mid;
			}else {
				copy[indexCopy--] = array[p2--];
			}
		}
		
		while(p1 >= start) {
			copy[indexCopy--] = array[p1--];
		}
		
		while(p2 >= mid+1) {
			copy[indexCopy--] = array[p2--];
		}
		
		for(int i = start; i <= end; i++) {
			array[i] = copy[i];
		}
		
		return leftCount + rightCount + count;
	}
		
	public static void main(String[] args) {
		int[] nums = {1,2,3,4,5,6,7,0};
		System.out.println(InversePairs(nums));
	}
}

总结

归并算法的思想