首页 > 试题广场 > 数组中的逆序对
[编程题]数组中的逆序对
  • 热度指数:443055 时间限制:C/C++ 2秒,其他语言4秒 空间限制:C/C++ 32M,其他语言64M
  • 算法知识视频讲解
在数组中的两个数字,如果前面一个数字大于后面的数字,则这两个数字组成一个逆序对。输入一个数组,求出这个数组中的逆序对的总数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

输出

7
count = 0
class Solution:
    def InversePairs(self, data):
        global count
        def MergeSort(lists):
            global count
            if len(lists) <= 1:
                return lists
            num = int( len(lists)/2 )
            left = MergeSort(lists[:num])
            right = MergeSort(lists[num:])
            r, l=0, 0
            result=[]
            while l<len(left) and r<len(right):
                if left[l] < right[r]:
                    result.append(left[l])
                    l += 1
                else:
                    result.append(right[r])
                    r += 1
                    count += len(left)-l
            result += right[r:]
            result += left[l:]
            return result
        MergeSort(data)
        return count%1000000007


个人PC500ms内,牛客网就超时了,python本来就慢。归并算法内计数,Python2 没有nonlocal挺蛋疼的。

编辑于 2017-07-11 20:28:59 回复(16)
/*归并排序的改进,把数据分成前后两个数组(递归分到每个数组仅有一个数据项),
合并数组,合并时,出现前面的数组值array[i]大于后面数组值array[j]时;则前面
数组array[i]~array[mid]都是大于array[j]的,count += mid+1 - i
参考剑指Offer,但是感觉剑指Offer归并过程少了一步拷贝过程。
还有就是测试用例输出结果比较大,对每次返回的count mod(1000000007)求余
*/

public class Solution {
    public int InversePairs(int [] array) {
        if(array==null||array.length==0)
        {
            return 0;
        }
        int[] copy = new int[array.length];
        for(int i=0;i<array.length;i++)
        {
            copy[i] = array[i];
        }
        int count = InversePairsCore(array,copy,0,array.length-1);//数值过大求余
        return count;
        
    }
    private int InversePairsCore(int[] array,int[] copy,int low,int high)
   	{
        if(low==high)
        {
            return 0;
        }
        int mid = (low+high)>>1;
        int leftCount = InversePairsCore(array,copy,low,mid)%1000000007;
        int rightCount = InversePairsCore(array,copy,mid+1,high)%1000000007;
        int count = 0;
        int i=mid;
        int j=high;
        int locCopy = high;
        while(i>=low&&j>mid)
        {
            if(array[i]>array[j])
            {
                count += j-mid;
                copy[locCopy--] = array[i--];
                if(count>=1000000007)//数值过大求余
                {
                    count%=1000000007;
                }
            }
            else
            {
                copy[locCopy--] = array[j--];
            }
        }
        for(;i>=low;i--)
	    {
	        copy[locCopy--]=array[i];
	    }
	    for(;j>mid;j--)
	    {
	        copy[locCopy--]=array[j];
	    }
        for(int s=low;s<=high;s++)
        {
            array[s] = copy[s];
        }
        return (leftCount+rightCount+count)%1000000007;
    }
}
编辑于 2016-08-02 10:31:03 回复(90)
思路分析:
看到这个题目,我们的第一反应是顺序扫描整个数组。每扫描到一个数组的时候,逐个比较该数字和它后面的数字的大小。如果后面的数字比它小,则这两个数字就组成了一个逆序对。假设数组中含有n个数字。由于每个数字都要和O(n)这个数字比较,因此这个算法的时间复杂度为O(n^2)。
我们以数组{7,5,6,4}为例来分析统计逆序对的过程。每次扫描到一个数字的时候,我们不拿ta和后面的每一个数字作比较,否则时间复杂度就是O(n^2),因此我们可以考虑先比较两个相邻的数字。

(a) 把长度为4的数组分解成两个长度为2的子数组;
(b) 把长度为2的数组分解成两个成都为1的子数组;
(c) 把长度为1的子数组 合并、排序并统计逆序对
(d) 把长度为2的子数组合并、排序,并统计逆序对;
在上图(a)和(b)中,我们先把数组分解成两个长度为2的子数组,再把这两个子数组分别拆成两个长度为1的子数组。接下来一边合并相邻的子数组,一边统计逆序对的数目。在第一对长度为1的子数组{7}、{5}中7大于5,因此(7,5)组成一个逆序对。同样在第二对长度为1的子数组{6}、{4}中也有逆序对(6,4)。由于我们已经统计了这两对子数组内部的逆序对,因此需要把这两对子数组 排序 如上图(c)所示, 以免在以后的统计过程中再重复统计。
接下来我们统计两个长度为2的子数组子数组之间的逆序对。合并子数组并统计逆序对的过程如下图如下图所示。
我们先用两个指针分别指向两个子数组的末尾,并每次比较两个指针指向的数字。如果第一个子数组中的数字大于第二个数组中的数字,则构成逆序对,并且逆序对的数目等于第二个子数组中剩余数字的个数,如下图(a)和(c)所示。如果第一个数组的数字小于或等于第二个数组中的数字,则不构成逆序对,如图b所示。每一次比较的时候,我们都把较大的数字从后面往前复制到一个辅助数组中,确保 辅助数组(记为copy) 中的数字是递增排序的。在把较大的数字复制到辅助数组之后,把对应的指针向前移动一位,接下来进行下一轮比较。
过程:先把数组分割成子数组,先统计出子数组内部的逆序对的数目,然后再统计出两个相邻子数组之间的逆序对的数目。在统计逆序对的过程中,还需要对数组进行排序。如果对排序算法很熟悉,我们不难发现这个过程实际上就是归并排序。参考代码如下:
class Solution {
public:
    int InversePairs(vector<int> data) {
       int length=data.size();
        if(length<=0)
            return 0;
       //vector<int> copy=new vector<int>[length];
       vector<int> copy;
       for(int i=0;i<length;i++)
           copy.push_back(data[i]);
       long long count=InversePairsCore(data,copy,0,length-1);
       //delete[]copy;
       return count%1000000007;
    }
    long long InversePairsCore(vector<int> &data,vector<int> &copy,int start,int end)
    {
       if(start==end)
          {
            copy[start]=data[start];
            return 0;
          }
       int length=(end-start)/2;
       long long left=InversePairsCore(copy,data,start,start+length);
       long long right=InversePairsCore(copy,data,start+length+1,end);  
       
       int i=start+length;
       int j=end;
       int indexcopy=end; 
       long long count=0;
       while(i>=start&&j>=start+length+1)
          {
             if(data[i]>data[j])
                { 
                  copy[indexcopy--]=data[i--]; 
                  count=count+j-start-length;          //count=count+j-(start+length+1)+1;
                }
             else
                { 
                  copy[indexcopy--]=data[j--]; 
                }           
          }
       for(;i>=start;i--)
           copy[indexcopy--]=data[i]; 
       for(;j>=start+length+1;j--)
           copy[indexcopy--]=data[j];        
       return left+right+count;
    }
};

编辑于 2018-05-04 10:25:36 回复(88)
public class Solution {
    int cnt;

	public int InversePairs(int[] array) {
		cnt = 0;
		if (array != null)
			mergeSortUp2Down(array, 0, array.length - 1);
		return cnt;
	}

	/*
	 * 归并排序(从上往下)
	 */
	public void mergeSortUp2Down(int[] a, int start, int end) {
		if (start >= end)
			return;
		int mid = (start + end) >> 1;

		mergeSortUp2Down(a, start, mid);
		mergeSortUp2Down(a, mid + 1, end);

		merge(a, start, mid, end);
	}

	/*
	 * 将一个数组中的两个相邻有序区间合并成一个
	 */
	public void merge(int[] a, int start, int mid, int end) {
		int[] tmp = new int[end - start + 1];

		int i = start, j = mid + 1, k = 0;
		while (i <= mid && j <= end) {
			if (a[i] <= a[j])
				tmp[k++] = a[i++];
			else {
				tmp[k++] = a[j++];
				cnt += mid - i + 1;  // core code, calculate InversePairs............
			}
		}

		while (i <= mid)
			tmp[k++] = a[i++];
		while (j <= end)
			tmp[k++] = a[j++];
		for (k = 0; k < tmp.length; k++) 
			a[start + k] = tmp[k];
	}
}

发表于 2016-03-07 21:18:57 回复(68)
//大家好,我是yishuihan
/*参考《剑指offer》,有两种思路。第一就是暴力求解法,时间复杂度为o(n^2),空间复杂度o(1)
第二种思路就是使用归并排序的思想进行处理,时间复杂度o(nlog(n)),空间复杂度0(n)*/
class Solution {
public:
    int InversePairs(vector<int> data) {
        if(data.size()<=1) return 0;//如果少于等于1个元素,直接返回0
        int* copy=new int[data.size()];
        //初始化该数组,该数组作为存放临时排序的结果,最后要将排序的结果复制到原数组中
        for(unsigned int i=0;i<data.size();i++)
            copy[i]=0;
        //调用递归函数求解结果
        int count=InversePairCore(data,copy,0,data.size()-1);
        delete[] copy;//删除临时数组
        return count;
    }
     //程序的主体函数
    int InversePairCore(vector<int>& data,int*& copy,int start,int end)
    {
        if(start==end)
        {
            copy[start]=data[start];
            return 0;
        }
        //将数组拆分成两部分
        int length=(end-start)/2;//这里使用的下标法,下面要用来计算逆序个数;也可以直接使用mid=(start+end)/2
        //分别计算左边部分和右边部分
        int left=InversePairCore(data,copy,start,start+length)%1000000007;
        int right=InversePairCore(data,copy,start+length+1,end)%1000000007;
        //进行逆序计算
        int i=start+length;//前一个数组的最后一个下标
        int j=end;//后一个数组的下标
        int index=end;//辅助数组下标,从最后一个算起
        int count=0;
        while(i>=start && j>=start+length+1)
        {
            if(data[i]>data[j])
            {
                copy[index--]=data[i--];
                //统计长度
                count+=j-start-length;
                if(count>=1000000007)//数值过大求余
                    count%=1000000007;
            }
            else
            {
                copy[index--]=data[j--];
            }
        }
        for(;i>=start;--i)
        {
            copy[index--]=data[i];
        }
        for(;j>=start+length+1;--j)
        {
            copy[index--]=data[j];
        }
        //排序
        for(int i=start; i<=end; i++) {
            data[i] = copy[i];
        }
        //返回最终的结果
        return (count+left+right)%1000000007;
    }
};

编辑于 2016-08-05 11:33:29 回复(8)
# -*- coding:utf-8 -*-
class Solution:
    def InversePairs(self, data):
        # write code here
        count = 0
        copy = []
        for i in data:
            copy.append(i)
        copy.sort()
        
        for i in range(len(copy)):
            count += data.index(copy[i])
            data.remove(copy[i])
            
        return count%1000000007

#我惊呆了,就是通不过,这没多复杂吧我的哥

发表于 2017-12-29 21:12:14 回复(12)

这道题目使用python通不过,建议把判定时间增长一点

发表于 2017-10-31 21:58:30 回复(24)
Pis头像 Pis
略微修改了书上的思路,直接归并将序排列,这样可以从头开始比较。其余思路一样
class Solution {
public:
	long countRes ;
    int InversePairs(vector<int> data) {
		countRes = 0;
		if(data.size() == 0)
			return 0;
		MergeSort(data,0,data.size()-1);
		return countRes%1000000007 ;
    }
	
	void MergeSort(vector<int>& data,int first,int end){
		if(first < end){
			int mid = (first + end)/2;
			MergeSort(data,first,mid);
			MergeSort(data,mid+1,end);
			vector<int> tmp;
			MergeArray(data,first,mid,end,tmp);
		}
	}
	void MergeArray(vector<int>& data,int first,int mid,int end,vector<int> tmp){
		int i = first;int m = mid;
		int j = mid + 1;int n = end;
	
		while(i<=m && j<=n){
			if(data[i] > data[j]){
				tmp.push_back(data[i++]);
				countRes += n - j + 1;
			}
			else{
				tmp.push_back(data[j++]);
			}
		}
		while(i<=m)
			tmp.push_back(data[i++]);
		while (j<=n)
			tmp.push_back(data[j++]);

		//更新data数组
		int k = 0;
		for (int i = first; i <= end &&k<tmp.size(); i++)
			data[i] = tmp[k++];
		
	}
};

编辑于 2016-07-19 19:34:19 回复(5)
啥头像
参考《剑指offer》用归并排序的思想, 时间复杂度O(nlogn)

代码如下:
int InversePairs(vector<int> data) {
        int length  = data.size();
        return mergeSort(data, 0, length-1);
    }

    int mergeSort(vector<int>& data, int start, int end) {
        // 递归终止条件
        if(start >= end) {
            return 0;
        }

        // 递归
        int mid = (start + end) / 2;
        int leftCounts = mergeSort(data, start, mid);
        int rightCounts = mergeSort(data, mid+1, end);

        // 归并排序,并计算本次逆序对数
        vector<int> copy(data); // 数组副本,用于归并排序
        int foreIdx = mid;      // 前半部分的指标
        int backIdx = end;      // 后半部分的指标
        int counts = 0;         // 记录本次逆序对数
        int idxCopy = end;      // 辅助数组的下标
        while(foreIdx>=start && backIdx >= mid+1) {
            if(data[foreIdx] > data[backIdx]) {
                copy[idxCopy--] = data[foreIdx--];
                counts += backIdx - mid;
            } else {
                copy[idxCopy--] = data[backIdx--];
            }
        }
        while(foreIdx >= start) {
            copy[idxCopy--] = data[foreIdx--];
        }
        while(backIdx >= mid+1) {
            copy[idxCopy--] = data[backIdx--];
        }
        for(int i=start; i<=end; i++) {
            data[i] = copy[i];
        }

        return (leftCounts+rightCounts+counts);
    }

发表于 2015-08-29 14:13:14 回复(17)
class Solution {
public:
    int InversePairs(vector<int> data) {
        if(data.size()==0)
            return 0;
        vector<int> copy(data);    // 辅助数组,每次递归后有序
        return InversePairsCore(data, copy, 0, data.size()-1);
    }

    int InversePairsCore(vector<int>& data, vector<int>& copy, int begin, int end) {
        if(begin == end)
            return 0;
        int mid = begin + (end-begin)/2;
        int left = InversePairsCore(copy, data, begin, mid);
        int right = InversePairsCore(copy, data, mid+1, end);
        
        int last_in_left = mid;		// 比较从尾端开始
        int last_in_right = end;	// 比较从尾端开始
        int index_copy = end; 		// 比较结果存入辅助数组尾端
        long res = 0;
        
        // 归并排序:相当于两个有序数组合成一个有序表(从尾端开始是为了计数)
        while(last_in_left>=begin && last_in_right>=mid+1) {
            if(data[last_in_left] > data[last_in_right]) {
                copy[index_copy--] = data[last_in_left--];
                res += last_in_right - mid;
            }
            else 
                copy[index_copy--] = data[last_in_right--];
        }
        
        while(last_in_left >= begin)
            copy[index_copy--] = data[last_in_left--];
        while(last_in_right >= mid+1)
            copy[index_copy--] = data[last_in_right--];
        
        return (left+right+res) % 1000000007;
    }
};
发表于 2017-07-26 21:51:02 回复(2)
代码参考剑指offer
----------------------------------------------------------------
2016.08.02更新
class Solution {
public:
    long long InversePairsCore(vector<int> &data,vector<int>&copy,int start,int end)
    {
        if(start==end)
        {
            copy[start]=data[start];
            return 0;
        }
        int length = (end-start)/2;
        long long left = InversePairsCore(copy,data,start,start+length);
        long long right = InversePairsCore(copy,data,start+length+1,end);
          
        int i = start + length;
        int j = end;
        int indexCopy = end;
        long long  count=0;
        while(i>=start&&j>=start+length+1)
        {
            if(data[i]>data[j])
            {
                copy[indexCopy--]=data[i--];
                count+=j-start-length;
            }
            
            else
            {
                copy[indexCopy--]=data[j--];
            }
        }
        for(;i>=start;--i)
            copy[indexCopy--] = data[i];
        for(;j>=start+length+1;--j)
            copy[indexCopy--] = data[j];
        return left+right+count;
        }
    int InversePairs(vector<int> data) {
        int length = data.size();
        if(length<=0)
            return 0;
        vector<int> copy;
        for(int i=0;i<length;i++)
            copy.push_back(data[i]);
        long long  count = InversePairsCore(data,copy,0,length-1);
        copy.clear();
        return count%1000000007;
    }
     
     
};

编辑于 2016-08-02 17:21:55 回复(12)

题目描述

image

解题思路

这个之前的笔记中已经说过这道题目了,是归并排序的典型应用。归并排序的基本思想是分治,在治的过程中有前后数字的大小对比,此时就是统计逆序对的最佳时机。

我的答案

public class Solution {
    //统计逆序对的个数
    int cnt;
    public int InversePairs(int [] array) {
        if(array.length != 0){
            divide(array,0,array.length-1);
        }
        return cnt;
    }

    //归并排序的分治---分
    private void divide(int[] arr,int start,int end){
        //递归的终止条件
        if(start >= end)
            return;
        //计算中间值,注意溢出
        int mid = start + (end - start)/2;

        //递归分
        divide(arr,start,mid);
        divide(arr,mid+1,end);

        //治
        merge(arr,start,mid,end);
    }

    private void merge(int[] arr,int start,int mid,int end){
        int[] temp = new int[end-start+1];

        //存一下变量
        int i=start,j=mid+1,k=0;
        //下面就开始两两进行比较,若前面的数大于后面的数,就构成逆序对
        while(i<=mid && j<=end){
            //若前面小于后面,直接存进去,并且移动前面数所在的数组的指针即可
            if(arr[i] <= arr[j]){
                temp[k++] = arr[i++];
            }else{
                temp[k++] = arr[j++];
                //a[i]>a[j]了,那么这一次,从a[i]开始到a[mid]必定都是大于这个a[j]的,因为此时分治的两边已经是各自有序了
                cnt = (cnt+mid-i+1)%1000000007;
            }
        }
        //各自还有剩余的没比完,直接赋值即可
        while(i<=mid)
            temp[k++] = arr[i++];
        while(j<=end)
            temp[k++] = arr[j++];
        //覆盖原数组
        for (k = 0; k < temp.length; k++)
            arr[start + k] = temp[k];
    }
}
编辑于 2019-03-10 14:31:16 回复(4)
/*
*归并排序的思想,最后求得的逆序数进行取摸 % 1000000007 
*/
public class Solution {
   public int InversePairs(int [] array) {
	        if(array==null || array.length<=0){
	            return 0;
	        }
	        int pairsNum=mergeSort(array,0,array.length-1);
	        return pairsNum;
	    }
	    
	    public int mergeSort(int[] array,int left,int right){
	        if(left==right){
	        	return 0;   
	        }
	        int mid=(left+right)/2;
	        int leftNum=mergeSort(array,left,mid);
	        int rightNum=mergeSort(array,mid+1,right);
	        return (Sort(array,left,mid,right)+leftNum+rightNum)%1000000007;
	    }
	    
	    public int Sort(int[] array,int left,int middle,int right){
	        int current1=middle;
	        int current2=right;
	        int current3=right-left;
	        int temp[]=new int[right-left+1];
	        int pairsnum=0;
	        while(current1>=left && current2>=middle+1){
	            if(array[current1]>array[current2]){
	                temp[current3--]=array[current1--];
	                pairsnum+=(current2-middle);     //这个地方是current2-middle!!!!
	                if(pairsnum>1000000007)//数值过大求余
	                {
	                    pairsnum%=1000000007;
	                }
	            }else{
	                temp[current3--]=array[current2--];
	            }
	        }
	        while(current1>=left){
	            temp[current3--]=array[current1--];
	        }
	        while(current2>=middle+1){
	            temp[current3--]=array[current2--];
	        }
	        //将临时数组赋值给原数组
	        int i=0;
	        while(left<=right){
	            array[left++]=temp[i++];
	        }
	        return pairsnum;
	    }
}

发表于 2016-07-28 19:53:04 回复(6)
//这道题debug了好久才提交,总是出现各种问题,得到了很多教训,如注释中的1,2,3
//另外debug时,不仅要观察最后的结果,还要看数组是否真的排序了
class Solution {
public:
	int InversePairs(vector<int> data) {
        //用long long类型否则会超限
		long long num = 0;
		mergesort(data, num, data.begin(), data.end() - 1);
		return num%1000000007;
	}
    //归并排序
	void mergesort(vector<int> &data, long long &num, vector<int>::iterator start, vector<int>::iterator end) {
		if (start == end) return;
		vector<int>::iterator mid = start + (end - start) / 2;
		mergesort(data, num, start, mid);
		mergesort(data, num, mid + 1, end);
		merge(data, num, start, end);
	}
    //合并
	void merge(vector<int> &data, long long &num, vector<int>::iterator start, vector<int>::iterator end) {
		if (start == end) return;
		vector<int>::iterator mid = start + (end - start) / 2;
        //把要合并的两个子数组保存出来
		vector<int> data1(start, mid+1);
		vector<int> data2(mid + 1, end+1);
        //两个迭代器分别指向两个数组的末尾
		vector<int>::iterator p = data1.end() - 1;
		vector<int>::iterator q = data2.end() - 1;
		vector<int>::iterator m = end;
		int sz1 = data1.size();
		int sz2 = data2.size();
        //合并,当前面数组的元素大于后面时计数加一
		while (sz1>0&&sz2>0) {
			if (*q<*p) {
			    num = q - data2.begin()+ 1+num;//1、迭代器相减注意顺序
				*m = *p;
				--sz1;
				--m;
				if(sz1>0) --p;//2、有效迭代器的范围是[begin(),end()),begin()位置已经不可以再自减了
			}
			else {
				*m = *q;
				--sz2;
				--m;
				if(sz2>0)  --q;
			}
		}
        //3、把剩余的放入数组中,一开始分析出来其中一个数组最多只剩一个元素,而没有让迭代器自减
		while (sz1--) {
			*m = *p;
			if (sz1 > 0) {
				--m;
				--p;
			}			
		}		
		while (sz2--) {
			*m = *q;
			if (sz2 > 0) {
				--m;
				--q;
			}	
		}			
	}
};

发表于 2017-06-11 13:39:28 回复(0)
class Solution:
    def InversePairs(self, data):
        #发现可以用归并排序,归并拼接后用计算排序时元素的index变动了多少
        #两个有序序列,每个元素移动index数(严格来说不是移动,这里不知怎么表达)之和好像刚好等于逆序对的个数
        #我也不知为什么,找了半天发现了这个规律
        _,s=self.MergeSort(data)
        return s%1000000007
    
    def MergeSort(self,data):
        n=len(data)
        #递归基
        if n==1:return data, 0
        #分两半来排序
        part1,part2=data[:n//2],data[n//2:]
        sorted_part1,s1=self.MergeSort(part1)
        sorted_part2,s2=self.MergeSort(part2)
        #排序后拼接这两半,拼接后先计数,然后将两个有序序列合并
        s,sorted_temp=0,sorted_part1+sorted_part2
        #用p、q两个指针指向两段,计算q中每个元素离插入点的index差
        p,q,len1,len_all=0,sorted_temp.index(sorted_part2[0]),len(sorted_part1),len(sorted_temp)
        while p<len1 and q<len_all:
            #移动p使p成为插入排序的插入点,计算要移动多少个位置
            while p<len1:
                if sorted_temp[q]<sorted_temp[p]:
                    s+=len1-p
                    break
                p+=1
            q+=1
        #完成排序,并把排序后的内容回溯给上一级做准备
        l=[]
        p,q=0,sorted_temp.index(sorted_part2[0])
        while p<len1 and q<len_all:
            if sorted_temp[p]<sorted_temp[q]:
                l.append(sorted_temp[p])
                p+=1
            else:
                l.append(sorted_temp[q])
                q+=1
        if p==len1:l+=sorted_temp[q:]
        if q==len_all:l+=sorted_part1[p:]
        return l,s+s1+s2
嗯?貌似应该是剑指里的最难题。一开始用暴力的方法是不能通过的,思路想了很久,毕竟和顺序有关,就考虑了下排序,觉得就归并会有地方发挥,手动模拟了下果然也可以,于是就用归并了。通过后刚也进来看了下答案,挺有成就感的。这次的复杂度,在自己电脑这边弄到几千个数都能短时间内跑出来

另外说下就是,python判题时间似乎不够,我第一次是运气好才通过,后来试了好几次都超时,然后才通过第二次。感觉这个判题时间有点迷。一次不行多试几次就好了
编辑于 2019-03-16 17:12:02 回复(0)
这道题有毒,用python,就算是直接return 2519,也会是超时...
    def InversePairs(self, data):
        # write code here
        #
        # import pdb
        # pdb.set_trace()
        res = 2519
        #res = self.merge_sort(0, len(self.data) - 1)
        return res

发表于 2018-02-10 15:04:32 回复(6)
//运行时间296ms 内存5361k 第一次接触归并排序思想 学习了 参考大神的
//我是菜鸟我怕谁 QAQ

    int count=0;
    public int InversePairs(int [] array) {
        if(array==null||array.length<=0) return 0;
        mergeUp2Down(array,0,array.length-1);
        return count;
    }
    public void mergeUp2Down(int [] a,int start,int end){
        if(start>=end) return;
        int mid=(end+start)>>1;
        mergeUp2Down(a,start,mid);
        mergeUp2Down(a,mid+1,end);
        merge(a,start,mid,end);
    }
    public void merge(int [] a,int start,int mid,int end){
        int[] temp=new int[end-start+1];
        int i=start,j=mid+1,index=0;
        while(i<=mid&&j<=end){
            if(a[i]>a[j]) {
                temp[index++]=a[j++];
                count+=mid-i+1;
                count=count>1000000007?count%1000000007:count;
            }else temp[index++]=a[i++];
        }
        while(i<=mid) temp[index++]=a[i++];
        while(j<=end) temp[index++]=a[j++];
        for(int k=0;k<temp.length;k++) a[start+k]=temp[k];
    }

编辑于 2017-05-09 02:42:51 回复(3)
感谢测试君更新了一下数据哈~
这个数据范围就正常多了。其实这个题目是可以有重复数字的,答案也在long long范围内(n*(n+1)/2)。
原来不离散化用map的已经超时了,所以还是老老实实离散化了,当然归并排序的方法就不用了。
O(n*log(n))
#define lb(x) ((x) & -(x))
typedef long long ll;
classBIT{
public:
    intn;
    vector<int> a;
    BIT(intn) : n(n), a(n + 1, 0){}
    voidadd(inti, intv){
        for(; i <= n; i += lb(i)) a[i] += v;
    }
    ll sum(inti){
        intr = 0;
        for(; i; i -= lb(i)) r += a[i];
        returnr;
    }
};
 
classSolution {
public:
    intInversePairs(vector<int> d) {
        intn = d.size();
        vector<int> t(d);
        sort(t.begin(), t.end()); //排序
        t.erase(unique(t.begin(), t.end()), t.end()); //去除重复元数(当然这题没有重复元素)
        for(inti = 0; i < n; ++i) //离散化
            d[i] = lower_bound(t.begin(), t.end(), d[i]) - t.begin() + 1;
        BIT bit(t.size());
        ll ans = 0;
        for(inti = n - 1; i >= 0; --i){
            ans += bit.sum(d[i] - 1);
            bit.add(d[i], 1);
        }
        returnans % 1000000007;
    }
};


=============================================

UPD: 看到有人用个数组暴力维护了大于0-8的数。。。原来数据才个位数啊。。。。我一口老血喷了出来,不做了,睡觉!


=============================================
经典问题,可以用归并排序(分治)或数状数组维护一下
数据这么小我也懒得离散化了,,直接用个map....(一脸紧张

#define lb(x) ((x) & -(x))
class BIT{
    int n;
    map<int, int> d;
public:
    BIT(int n_) : n(n_) {}
    void add(int i, int v){
        for(; i <= n; i += lb(i)) d[i] += v;
    }
    int sum(int i){
        int r = 0;
        for(; i; i -= lb(i)) r += d[i];
        return r;
    }
};
class Solution {
public:
    int InversePairs(vector<int> d) {
        int mi = 0x7fffffff, mx = 0x80000000;
        for(int i = 0; i < d.size(); ++i) mi = min(mi, d[i]), mx = max(mx, d[i]);
        int r = 0;
        BIT bit(mx - mi + 5);
        for(int i = (int)d.size() - 1; i >= 0; --i){
            r += bit.sum(d[i] - mi);
            bit.add(d[i] - mi + 1, 1);
        }
        return r;
    } };


//本来是个经典问题
//这么暴力都能通过。。。 数据规模竟然这么小。。。那这题目出来何用。。。
class Solution {
public:
    int InversePairs(vector<int> d) {
        int r = 0;
        for(int i = 0; i < d.size(); ++i){
            for(int j = 0; j < i; ++j) if(d[j] > d[i]) ++r;
        }
        return r;
    }
};


编辑于 2016-07-23 03:49:09 回复(24)
class Solution {
public:
	int InversePairs(vector<int> data) {
		return mergeSort(data, 0, data.size() - 1);
	}
private:
	long long mergeSort(vector<int> &data, int s, int e) {
		if (s >= e) return 0;
		int mid = (e - s) / 2 + s;
		long long num = mergeSort(data, s, mid) + mergeSort(data, mid + 1, e);
		int i = s, j = mid + 1;
		int cnt = 0;
		vector<int> tmp;
		while (i <= mid || j <= e) {
			if (i > mid) {
				tmp.push_back(data[j++]);
			}
			else if (j > e) {
				num += cnt;
				tmp.push_back(data[i++]);
			}
			else if (data[i] > data[j]) {
				cnt++;
				tmp.push_back(data[j++]);
			}
			else {
				num += cnt;
				tmp.push_back(data[i++]);
			}
		}
		for (int i = s; i <= e; ++i) {
			data[i] = tmp[i - s];
		}
		return num%1000000007;
	}
};

发表于 2017-06-10 20:46:32 回复(0)

归并排序走一遍 合并时对于右边的数统计一下左边比他小的个数,此个数即为逆序对个数。

class Solution {
public:
    void solve(int x, int y, vector<int> &A, vector<int> &B, int &ans){//B为临时空间
        if(y - x > 1){
            int mid = x + (y - x)/2, left = x, right = mid, i = x;
            solve(x, mid, A, B, ans);
            solve(mid, y, A, B, ans);
            int zuo = mid - x;
            while(left < mid || right < y){
                if(right >= y || (left < mid && A[left] < A[right]))
                    {B[i++] = A[left++];zuo--;}
                else {B[i++] = A[right++];ans = (ans+zuo)%1000000007;}
            }
        }
    for(int i = x; i < y; i++) A[i] = B[i];
}
   int InversePairs(vector<int> data) {
        vector<int> tmp = data;
        int ans = 0;
        solve(0, data.size(), data, tmp, ans);
        return ans;
    }
};
发表于 2018-12-11 20:33:58 回复(0)