【剑指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));
}
}
总结
归并算法的思想
下一篇: 剑指Offer-51 数组中的逆序对
推荐阅读
-
剑指offer31:整数中1出现的次数(从1到n整数中1出现的次数)
-
剑指offer28:找出数组中超过一半的数字。
-
剑指offer27:按字典序打印出该字符串中字符的所有排列
-
C#版剑指Offer-001二维数组中的查找
-
剑指offer11:输入一个整数,输出该数二进制表示中1的个数。其中负数用补码表示。(进制转换,补码反码)
-
剑指offer JZ31 整数中1出现的次数 Python 解
-
剑指offer JZ54 字符流中第一个不重复的字符 Python 多解
-
剑指Offer积累-JZ1-二维数组中的查找
-
剑指offer之队列中的最大值(C++/Java双重实现)
-
剑指offer之在排序数组中查找数字 I(C++/Java双重实现)