即日起在codingBlog上分享您的技术经验即可获得积分,积分可兑换现金哦。

数组里的逆序对(java版)

编程语言 ouyangyanlan 9℃ 0评论

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

【输入描述】题目保证输入的数组中没有的相同的数字


数据范围:


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


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


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

【输入样例】


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

【输出样例】


7

注:从题目描述来看,测试数据会非常大,单纯的暴力循环会超时


【解题思路】


//1. 利用二路归并排序的思想。


//2. 在二路归并排序中,若左子区间的某个数a[i]>a[j]右子区间的某个数,则从a[i~center]都是大于a[j]的,所以逆序数也就等于count +=center-i+1,这里center为左子区间的最后一个值的下标。

public class Solution {
    private long count;
    public int InversePairs(int [] array) {
        if(array==null || array.length==0){
            return 0;
        }
        count = 0;
        mergeSort(array, 0, array.length-1);
        int c = new Long(count%1000000007).intValue();
        return c;
    }

    public void mergeSort(int[] input, int left, int right){
        int mid = (left + right) / 2;  
        if (left < right) {  
            // 左边  
            mergeSort(input,left,mid);  
            // 右边  
            mergeSort(input,mid+1,right);  
            // 左右归并  
            sort(input,left,mid,right);
        }
    }

    public void sort(int[] input, int left, int center, int right){
        int []tempArray = new int[right-left+1];
        int mid = center+1;
        int temp = left;
        int current = 0;
        while(left<=center && mid<=right){
            if(input[left]>input[mid]){
                tempArray[current++]=input[mid++];        
                count +=center-left+1;
            }else{
                tempArray[current++]=input[left++];
            }
        }
        //只会执行一个
        while(left<=center){
            tempArray[current++]=input[left++];
        }
        while(mid<=right){
            tempArray[current++]=input[mid++];
        }
        current=0;
        while(temp<=right){
            input[temp++]=tempArray[current++];
        }
    }
}

转载请注明:CodingBlog » 数组里的逆序对(java版)

喜欢 (0)or分享 (0)
发表我的评论
取消评论

*

表情