数组中的逆序对 2023-11-20 07:37 134阅读 0赞 一、题目 在数组中，如果前一个数字大于后一个数字，则两个数字组成一个逆序对。输入一个数组，求逆序对总数。 二、分析 （1）暴力求解：顺序扫描这个数组，每扫描到一个数字，如果后面是的数字比当前的数字小，则构成一个逆序对。 （2）归并排序（先把数组分成子数组，统计出子数组中逆序对的个数，再统计出相邻子数组中逆序对的个数） int inversepair(int *nums,int length) { if(num==nullptr||length<=0)return 0; int *tmp=new int[length]; for(int i=0;i<length;++i) { tmp[i]=nums[i]; } int count=inversepair(nums,tmp,0,length-1); delete []tmp; retrun count; } int inversepair(int *nums,int *tmp,int left,int right) { if(left==right) { tmp[left]=nums[left]; return 0; } int len=(right-left)>>2; int l=inversepair(nums,tmp,left,left+len); int r=inversepair(nums,tmp,left+len+1,right); int li=left+len; int ri=right; int count=0; int tmpindex=end; while(li>=left&&ri>=left+len+1) { if(nums[li]>nums[ri]) { tmp[tmpindex--]=nums[li--]; count+=ri-left-len;z } else { tmp[tmpindex--]=nums[ri--]; } } for(;li>=left;--li) tmp[tmpindex--]=nums[li]; for(;ri>=left+len+1;ri--) tmp[tmpindex--]=nums[ri]; return left+right+count; }
还没有评论，来说两句吧...