剑指Offer51:数组中的逆序对
程序员文章站
2022-07-10 12:16:58
...
题目:在数组中的两个数字,如果前面一个数字大于后面的数字,则这两个数字组成一个逆序对。输入一个数组,求出这个数组中的逆序对的总数P。
eg:输入数组 7,5,6,4.共存在5个逆序对,{7,6},{7,5},{7,4},{6,4},{5,4}。
暴力法,即第一次遍历n个数的过程中,从n+1…往下,时间复杂度是O(n2)。
书上的更快的方法:即借助,归并排序的思想,将数组划分成为2个子数组,再在2个子数组的基础上继续划分为4个子数组,直到每个子数组中只含有1个数的时候,停止划分(这里应该是边界条件),继续判断逻辑
当含有2个子数组时,7大于5,count+1.6大于4的时候count+1.然后p1指向子数组{5,7}中的7,p2指向{4,6}中的6,并且再设立辅助数组,当p1>p2,时,count加上p2(包含p2本身)之前的所有元素个数。再将p1放入辅助数组中,p3指向当前元素,再p1,p3指针同时减1.再判断,p1>p2?,不大于,将p2直接放入辅助数组中,同时,p2,p3减1.当p1为空时,p2不为空,就直接将p2剩余的元素放入辅助数组就好了。
书上代码:
public int InversePair(int[] array){
int len = array.length;
if(array == null || len <= 0){
return 0;
}
return mergSort(array,0,len-1);
}
public int mergSort(int[] array,int start,int end){
//就一条件
if(start == end)
{
return 0;
}
int mid = (start + end) / 2;
int left_count = mergSort(array,start,mid);
int right_count = mergSort(array,mid+1,end);
int i = mid,j = end;
//新建了数组
int[] copy =new int[end-start+1];
int copy_index = end-start;
int count = 0;
while(i >= start && j >= mid + 1){
if(array[i] > array[j]){
copy[copy_index--] = array[i--];
count += j-mid;
}else{
copy[copy_index--] = array[j--];
}
}
while(i >= start){
copy[copy_index--] = array[i--];
}
while(j >= mid+1){
copy[copy_index--] = array[j--];
}
i = 0;
while(start <= end){
array[start++] = copy[i++];
}
return left_count+right_count+count;
}
public static void main(String[] args) {
int[] nums = {7,5,6,4};
System.out.println(new MergSort().InversePair(nums));
}