JAva実装——配列中の逆シーケンス対(剣指offer原題)

テーマ:配列の中の2つの数字で、前の1つの数字が後ろの数字より大きい場合、この2つの数字は逆の順序のペアを構成します.1つの配列を入力し,この配列における逆順対の総数Pを求める.P対1000000007型取りの結果を出力します.出力P%1 000000007
牛客の上のテーマは1つの型取りの要求を追加して、妨げないで、求める数の後で型を取るだけでいいです.
この問題は集計ソートの応用で、以下の集計ソートを復習します~

public class MergeSortTest {
    public static void main(String[] args) {
        int[] data = new int[] { 5, 3, 6, 2, 1, 9, 4, 8, 7 };
        print(data);
        mergeSort(data);
        System.out.println("      ：");
        print(data);
    }
    public static void mergeSort(int[] data) {
        sort(data, 0, data.length - 1);
    }
    public static void sort(int[] data, int left, int right) {
        if (left >= right)
            return;
        //       
        int center = (left + right) / 2;
        //          
        sort(data, left, center);
        //          
        sort(data, center + 1, right);
        //   
        merge(data, left, center, right);
        print(data);
    }
    /*
    * @param data
    *     
    * @param left
    *             
    * @param center
    *              ，center+1             
    * @param right
    *             
    */
    public static void merge(int[] data, int left, int center, int right) {
    //     
        int[] tmpArr = new int[data.length];
    //           
        int mid = center + 1;
    // third          
        int third = left;
    //              
        int tmp = left;
        while (left <= center && mid <= right) {
    //                  
            if (data[left] <= data[mid]) {
                tmpArr[third++] = data[left++];
            } else {
                tmpArr[third++] = data[mid++];
            }
        }
    //             （      while         ）
        while (mid <= right) {
            tmpArr[third++] = data[mid++];}
        while (left <= center) {
            tmpArr[third++] = data[left++];
        }
    //                 
    // （  left-right             ）
        while (tmp <= right) {
            data[tmp] = tmpArr[tmp++];
        }
    }
    public static void print(int[] data) {
        for (int i = 0; i < data.length; i++) {
            System.out.print(data[i] + "\t");
        }
        System.out.println();
    }

}

出力結果:

5	3	6	2	1	9	4	8	7	
3	5	6	2	1	9	4	8	7	
3	5	6	2	1	9	4	8	7	
3	5	6	1	2	9	4	8	7	
1	2	3	5	6	9	4	8	7	
1	2	3	5	6	4	9	8	7	
1	2	3	5	6	4	9	7	8	
1	2	3	5	6	4	7	8	9	
1	2	3	4	5	6	7	8	9	
      ：
1	2	3	4	5	6	7	8	9

集計ソートの平均時間複雑度O(nlogn)は,問題に安定して戻り,集計時に集計個数をソートし,集計ソートを理解して注釈を結合すれば分かる.

public class test1 {
    public int result=0;
    public int InversePairs(int [] array) {
        mergeCount(array,0,array.length-1);
        return result;
    }
    public void mergeCount(int[] nums, int left, int right){
        if (left>=right) return;
        int mid=(right+left)/2;
        mergeCount(nums,left,mid);
        mergeCount(nums,mid+1,right);
        merge(nums,left,mid,right);
    }

    private void merge(int[] nums, int left, int mid, int right) {
        int [] temp=new int[right-left+1];
        //mid          j         
        int k=0,i=left,j=mid+1;
        while(i<=mid&&j<=right)
        {
            //                         
            if (nums[i]<=nums[j])
            {
                //      
                temp[k++]=nums[i++];
            }
            //                                                       mid-i+1
            else{
                temp[k++]=nums[j++];
                result=(result+(mid-i+1))%1000000007;
            }
        }
        //                                          
        while(i<=mid)
            temp[k++]=nums[i++];
        while(j<=right)
            temp[k++] = nums[j++];
        //                
        for (int m=0;m<k;m++)
            nums[left+m]=temp[m];
    }
}