N35_数组中的逆序对

ゝ一纸荒年。 2023-08-17 17:36 114阅读 0赞

## 题目描述 ##

在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组,求出这个数组中的逆序对的总数P。并将P对1000000007取模的结果输出。 即输出P%1000000007

## 输入描述: ##

题目保证输入的数组中没有的相同的数字

数据范围：

对于%50的数据,size<=10^4

对于%75的数据,size<=10^5

对于%100的数据,size<=2\*10^5

示例1

## 输入 ##

1,2,3,4,5,6,7,0

## 输出 ##

package new_offer;
    /**
     * 题目描述
     * 在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。
     * 输入一个数组,求出这个数组中的逆序对的总数P。
     * 并将P对1000000007取模的结果输出。 即输出P%1000000007
     * 输入描述:
     * 题目保证输入的数组中没有的相同的数字
     * 数据范围：
    	对于%50的数据,size<=10^4
    	对于%75的数据,size<=10^5
    	对于%100的数据,size<=2*10^5
     * @author Sonya
     *思路：归并排序。先把数组分割成子数组，先统计出子数组内部的逆序对的数目，
     *然后再统计出两个相邻子数组之间的逆序对的数目。
     */
    public class N35_InversePairs {
    	
    
    	public int InversePairs(int [] array) {
    		if(array.length<=0) return 0;
    		int count=0;
    		int []copy=new int[array.length];
    		for(int i=0;i<array.length;i++) {
    			copy[i]=array[i];
    		}
    		count=InversePairsCore(array,copy,0,array.length-1);
    		return count;
        }
    	 public int InversePairsCore(int[]array,int []copy,int start,int end) {
    			if(start==end) {
    				copy[start]=array[start];
    				return 0;
    			};
    			int len=(end-start)/2;
    			int left=InversePairsCore(array,copy,start,start+len);
    			int right=InversePairsCore(array,copy,start+len+1,end);
    			int count=0;
    			int i=start+len;//i初始化为前半段最后一个数字的下标
    			int j=end;//j初始化为后半段最后一个数字的下标
    			int indexcopy=end;
    			while(i>=start&&j>=start+len+1) {
    				if(array[i]>array[j]) {
    				count+=j-start-len;	
    				if(count>=1000000007)//数值过大求余
                    {
                        count%=1000000007;
                    }
    				copy[indexcopy--]=array[i--];		
    				}
    				else {
    					copy[indexcopy--]=array[j--];
    				}
    			}
    			for(;i>=start;i--) {
    					copy[indexcopy--]=array[i];
    				}
    				for(;j>=start+len+1;j--) {
    					copy[indexcopy--]=array[j];
    				}
    				for(int s=start;s<=end;s++) {//将数组再复制回去保证下次的是正确的。
    				array[s]=copy[s];
    			}
    				return (left+right+count)%1000000007;
    		}
    
    	public static void main(String[] args) {
    		// TODO Auto-generated method stub
        int []a= {364,637,341,406,747,995,234,971,571,219,993,407,416,366,315,301,601,650,418,355,460,505,360,965,516,648,727,667,465,849,455,181,486,149,588,233,144,174,557,67,746,550,474,162,268,142,463,221,882,576,604,739,288,569,256,936,275,401,497,82,935,983,583,523,697,478,147,795,380,973,958,115,773,870,259,655,446,863,735,784,3,671,433,630,425,930,64,266,235,187,284,665,874,80,45,848,38,811,267,575};
        N35_InversePairs n35=new N35_InversePairs();
        int count=n35.InversePairs(a);
        System.out.println(count);
     
    	}
    }

转载于:https://www.cnblogs.com/kexiblog/p/11156994.html