数组中的逆序对_

~一念执着~

//这道题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)

Python

Gelivabilities

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)

牛客6627738号

这道题有毒，用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 回复(7)

马客(Mark)

感谢测试君更新了一下数据哈~

这个数据范围就正常多了。其实这个题目是可以有重复数字的，答案也在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 回复(25)

drdr

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)

C/C++

卷积神经网络哦

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

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 回复(1)

rs勿忘初心

思路分析：

看到这个题目，我们的第一反应是顺序扫描整个数组。每扫描到一个数组的时候，逐个比较该数字和它后面的数字的大小。如果后面的数字比它小，则这两个数字就组成了一个逆序对。假设数组中含有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 回复(102)

C/C++

菜丶转行可达鸭

归并排序

class Solution {
public:
    int InversePairs(vector<int> data) {
        long long int res = 0;
        mergesort(data,0,data.size(),res);
        return res%1000000007;
    }
    void mergesort(vector<int> &array,int low,int high,long long &res){
        if(high-low<2) return;
        int mid = (low+high)>>1;
        mergesort(array,low,mid,res);
        mergesort(array,mid,high,res);
        merge(array,low,mid,high,res);
    }
    void merge(vector<int> &arr,int low,int mid,int high,long long &res){
        vector<int>::iterator it1 = arr.begin()+low;
        vector<int>::iterator it2 = arr.begin()+mid;
        int len1 = mid-low;
        int len2 = high-mid;
        vector<int> temArr(len1);
        for(int i=0;i<len1;++i) temArr[i] = *(it1+i);
        int i=0,j=0,k=0;
        while(k<len1){
            if(j>=len2 || *(it2+j)<temArr[k]) {*(it1+i) = temArr[k];++k;++i;res+=(len2-j);}
            else {*(it1+i) = *(it2+j);++j;++i;}
        }
    }
};

发表于 2020-03-26 16:21:17 回复(0)

八分爱

class Solution {
private:
    long long res = 0;
    void merge_sort(vector<int> &data, vector<int> &copy, int beg, int end){
        if(beg>=end)
            return;
        int mid = beg + (end-beg)/2;
        merge_sort(data, copy, beg, mid);
        merge_sort(data,copy,mid+1,end);
        merge(data, copy, beg ,mid, end);
    }
    
    void merge(vector<int> &data, vector<int> &copy, int beg, int mid, int end){
        int cur = beg, left=beg, right=mid+1;
        while(left <= mid && right <= end){
            if(data[left] <= data[right]){
                copy[cur] = data[left];
                left++;
                cur++;
            }
            else{
                copy[cur] = data[right];
                right++;
                cur++;
                res += (mid-left+1);
                if(res > 1000000007)
                    res %= 1000000007;
            }
        }
        if(left>mid){
            while(right<=end){
                copy[cur] = data[right];
                cur++;
                right++;
            }
        }
        else{
            while(left<=mid){
                copy[cur] = data[left];
                cur++;
                left++;
            }
        }
        for(int i = beg; i <= end; i++)
            data[i] = copy[i];
        return;
    }
public:
    int InversePairs(vector<int> data) {
        vector<int> copy(data);
        merge_sort(data,copy,0,data.size()-1);
        return res;
    }

};

发表于 2019-10-05 13:55:16 回复(0)

chestnut7

python 归并排序

# -*- coding:utf-8 -*-
from collections import deque

class Solution:
    def __init__(self):
        self.count = 0

    def InversePairs(self, lis):
        # write code here
        self.mergeSort(lis)
        return self.count%1000000007

    def mergeSort(self, lis):
        if len(lis) <= 1:
            return lis
        middle = int(len(lis)//2)
        left = self.mergeSort(lis[:middle])
        right = self.mergeSort(lis[middle:])
        return self.merge(left, right)                       
    def merge(self, left,right):
        merged,left,right = deque(),deque(left),deque(right)
        while left and right:
            if left[0] > right[0]:
                self.count += len(left)
                merged.append(right.popleft())
            else:
                merged.append(left.popleft())
        if right:
            merged.extend(right)
        else:
            merged.extend(left)
        return merged

发表于 2018-08-14 17:18:41 回复(1)

却顾所来径

class Solution {
public:
    int InversePairs(vector<int> data) {
        if(data.size()==0)return 0;
        vector<int>copy(data);
        return merge(data,copy,0,data.size()-1);
    }
    int merge(vector<int>&data,vector<int>&copy,int l,int r){
    //因为copy数组和data数组传递的是引用，而内层的遍历都需要把copy数组排好序，
    //自然而然，上一层的data数组就排好序了，所以返回上一层时可以直接使用了 
        if(l==r)return 0;
        int mid=(r+l)/2;
        int left=merge(copy,data,l,mid);
    //注意，这里copy和data交换了顺序，所以内层遍历中copy数组会排好序从而导致返回外
    //层时data数组排好序 
        int right=merge(copy,data,mid+1,r);
        int i=mid;
        int j=r;
        int end=r;
        long count=0;//注意：int型只能通过50%的数据
        while(i>=l&&j>=mid+1){
            if(data[i]>data[j]){
                count+=j-mid; 
                copy[end--]=data[i--];
            }else{
                copy[end--]=data[j--];
            }
        }
        while(i>=l)
            copy[end--]=data[i--];
        while(j>=mid+1)
            copy[end--]=data[j--];
        return (left+right+count)%1000000007;
    }
};

发表于 2018-07-07 15:54:07 回复(0)

C/C++

是小叶啊

本地调试版

#include <iostream>
#include <vector>

using namespace std;

int temp[200001];
long long cnt = 0;

void merge(vector<int> &a, int start, int mid, int end)
{
    int i = start, j = mid + 1, index = 0;
    while (i <= mid && j <= end)
    {
        if (a[i] <= a[j])
            temp[index++] = a[i++];
        else
        {
            cnt += (mid - i + 1);
            temp[index++] = a[j++];
        }
    }
    while (i <= mid)temp[index++] = a[i++];
    while (j <= end)temp[index++] = a[j++];
    for (int i = 0; i < index; i++)
        a[start + i] = temp[i];
}

void mergesort(vector<int> &data, int start, int end)
{
    if (start < end)
    {
        int mid = (start + end) >> 1;
        mergesort(data, start, mid);
        mergesort(data, mid + 1, end);
        merge(data, start, mid, end);
    }
}

int InversePairs(vector<int> data)
{
    int len = data.size();
    if (!len)return 0;
    mergesort(data, 0, len - 1);
    return cnt % 1000000007;
}

int main()
{
    ios::sync_with_stdio(false);
    vector<int> a;
    int n, tmp;
    cin >> n;
    for (int i = 0; i < n; i++)
    {
        cin >> tmp;
        a.push_back(tmp);
    }
    cout << InversePairs(a);
    return 0;
}

发表于 2018-06-17 10:45:31 回复(2)

Java

阿拉要洗澡

public class Solution {

public int InversePairs(int [] array) {

if(array.length == 0 || array == null)

return 0;

int count = InversePairsCore(array,0,array.length-1);

return count;

}

//用归并排序思想

private int InversePairsCore(int [] array,int low, int high){

if(low < high){

int mid = (low+high)/2;

int leftCount = InversePairsCore(array,low, mid)%1000000007;

int rightCount = InversePairsCore(array,mid+1,high)%1000000007;

int count = 0;//计算数目

int i = mid;//左边部分

int j = high;//右边部分

int k = high-low;//辅助数组

int[] temp = new int[high-low+1];

//左右两部分都是从后往前计算

while(i>=low && j>mid){

if(array[i] > array[j]){

count += j-mid;

temp[k--] = array[i--];

if(count >= 1000000007)

count %= 1000000007;

}else{

temp[k--] = array[j--];

}

//添加剩下的前半部分到temp中

for(;i>=low;i--)

temp[k--] = array[i];

//添加剩下的后半部分到temp中

for(;j>mid;j--)

temp[k--] = array[j];

//将排好序的temp复制到array中

for(int v = 0; v < (high-low+1); v++)

array[low+v] = temp[v];

return (leftCount+rightCount+count)%1000000007;

}

return 0;

}

发表于 2017-06-14 16:28:58 回复(0)

Julius

class Solution {
public:
    int merge(vector<int>& array, int start, int mid, int end){
        vector<int> left;
        vector<int> right;
        for(int i = start; i<=mid; ++i)
            left.push_back(array[i]);
        for(int i = mid +1; i<=end; ++i)
            right.push_back(array[i]);
        int i = 0;
		int j = 0;
        int curr = start;
        int count = 0;
        while(i<left.size()&& j<right.size()){
            if(right[j] < left[i])
                array[curr++] = right[j++];
            else{
                count += j;
                array[curr++] = left[i++];
            }
        }
        while(i < left.size()){
            count += j;
            array[curr++] = left[i++];
        }
        return count;
    }
    int mergesort(vector<int>& array, int start, int end){
        if(start < end){
            int mid = start + (end - start)/2;
            int left = mergesort(array, start, mid);
            int right = mergesort(array, mid+1, end);
            int m = merge(array, start, mid, end);
            return left + right + m;
        }
        return 0;
    }
    int InversePairs(vector<int> data) {
        int len = data.size();
        if(len <=0)
            return 0;
      	return mergesort(data, 0 , len -1);
    }
};

发表于 2015-09-19 22:17:54 回复(0)

lizo

class Solution {
public:
    int InversePairs(vector<int> data) {
        vector<int> a(9,0);  //用一个辅助数组保存前面有多少个大于 0 - 8的数
		int sum = 0;
		for (int i = 0; i < data.size(); i++) {
			int tmp = data[i];
			sum += a[tmp];  
			for (int j = tmp - 1; j >= 0; j--)  //更新辅助数组的值
				a[j] += 1;
		}
		return sum;
	} 
};

编辑于 2015-08-17 16:36:24 回复(1)

Java

Mono_Chrome

public class Solution {
    public int InversePairs(int [] array) {
        if (array == null) {
            return 0;
        }
        return mergeSort(array, 0, array.length - 1);
    }

    public int mergeSort(int[] array, int left, int right) {
        if (left >= right) {
            return 0;
        }
        int mid = left + ((right - left) >> 1);
        int leftSum = mergeSort(array, left, mid);
        int rightSum = mergeSort(array, mid + 1, right);
        return (leftSum + rightSum + merge(array, left, mid, right)) % 1000000007;
    }

    public int merge(int[] array, int left, int mid, int right) {
        int p1 = left;
        int p2 = mid + 1;
        int[] help = new int[right - left + 1];
        int index = 0;
        int count = 0;
        while (p1 <= mid && p2 <= right) {
            if (array[p1] <= array[p2]) {
                help[index++] = array[p1++];
            } else {
                count += ((mid - p1 + 1) % 1000000007);
                help[index++] = array[p2++];
            }
        }
        while (p1 <= mid) {
            help[index++] = array[p1++];
        }
        while (p2 <= right) {
            help[index++] = array[p2++];
        }
        index = 0;
        for (int i = left; i <= right; i++) {
            array[i] = help[index++];
        }
        return count % 1000000007;
    }
}

发表于 2021-05-20 21:29:15 回复(0)

Java

njmd929008

public class Solution {

private int cnt = 0;

public int InversePairs(int [] array) {

//归并排序，Merge时发现left元素大于right元素，则cnt++

if (array.length < 2) {

return 0;

}

int lo = 0;

int hi = array.length - 1;

sort(array, lo, hi);

return cnt;

}

private void sort(int[] a, int lo, int hi) {

if (hi <= lo) {

return;

}

int mid = lo + (hi-lo)/2;

sort(a, lo, mid);

sort(a, mid+1, hi);

merge(a, lo, mid, hi);

}

private void merge(int[] a, int lo, int mid, int hi) {

int l = lo; //指向当前left元素(left为a[lo..mid])

int r = mid + 1; //指向当前right元素（right为a[mid+1..hi]）

int[] aux = new int[hi+1];

int k = lo;

while (k < hi+1) { //aux还没填充满——>说明还没Merge完

if (l > mid) { //左边耗尽

aux[k++] = a[r++];

} else if (r > hi) { //右边耗尽

aux[k++] = a[l++];

} else if (a[l] > a[r]) { //left元素大于right元素

cnt += mid - l + 1; //当前left元素及其右边元素都比当前right大

aux[k++] = a[r++];

} else {

aux[k++] = a[l++];

}

for (int x = lo; x < hi+1; x++) {

a[x] = aux[x];

}

发表于 2016-06-28 19:24:05 回复(0)

Python 3

Vivimore

归并排序思想
时间复杂度：O(nlogn) 空间复杂度：O(n)

class Solution:
    sum_ = 0
    def merge_sort(self, data):
        n = len(data)
        if n <= 1:
            return data
        mid = n // 2
        left = self.merge_sort(data[:mid])
        right = self.merge_sort(data[mid:])
        l, r = 0, 0
        temp = []
        while l < len(left) and r < len(right):
            if left[l] > right[r]:
                self.sum_ += len(left) - l
                temp.append(right[r])
                r += 1
            else:
                temp.append(left[l])
                l += 1
        temp += left[l:]
        temp += right[r:]
        return temp
    def InversePairs(self , data: List[int]) -> int:
        self.merge_sort(data)
        return self.sum_ % 1000000007

发表于 2022-05-16 12:48:11 回复(0)

Java

小灰灰QAQ

import java.util.Arrays;
public class Solution {
    
    static int reslut = 0;
    
    public static int InversePairs(int[] array) {
        sort(array, 0, array.length - 1);
        return reslut;
    }


    static void sort(int[] array, int l, int r) {
        if (l >= r)
            return;
        int mid = (l + r) / 2;
        sort(array, l, mid);
        sort(array, mid + 1, r);

        if (array[mid] > array[mid + 1]) {
            reslut += merge(array, l, mid, r);
            if(reslut>1000000007)
                reslut-=1000000007;
        }

    }

    static int merge(int[] array, int l, int mid, int r) {
        int tc = 0;
        int c = 0;
        int[] temp = Arrays.copyOfRange(array, l, r + 1);
        int i = l, j = mid + 1;
        for (int k = l; k <= r; k++) {
            if (i > mid) {
                array[k] = temp[j - l];
                j++;
            } else if (j > r) {
                array[k] = temp[i - l];
                c += tc;
                tc = 0;
                i++;
            } else if (temp[i - l] < temp[j - l]) {
                array[k] = temp[i - l];
                c += tc;
                tc = 0;
                i++;
            } else {
                array[k] = temp[j - l];
                tc += mid - i + 1;
                j++;

            }
        }
        return c;
    }
}

发表于 2022-02-23 14:17:11 回复(0)

C++

牛客998691862号

//思路：分治的思想。
//在合并有序数组时，当左边数组的指针移动至下一元素时，说明该指针的元素能够和右指针元素之前的所有元素构成逆序对关系。
//所以逆序对总数加上右边指针前的元素个数。
//https://leetcode-cn.com/problems/shu-zu-zhong-de-ni-xu-dui-lcof/solution/shu-zu-zhong-de-ni-xu-dui-by-leetcode-solution/
class Solution{
    private:
    int merge_sort(vector<int>& nums, int l, int r, vector<int>& tmp){ 
        //易错点：按引用传递，经常忘写&号，然后错误极为隐蔽，经常半天找不到错误。（堪比==写成=）
        if(l >= r - 1) return 0;
        long long count  = 0; //注意这里用int的话，结果会因为溢出而输出负数
        //分
        int m = (l + r) / 2;
        count += merge_sort(nums, l, m, tmp);
        count += merge_sort(nums, m, r, tmp);
        //治
        int p = l, q = m, k = l; //使用双指针合并有序数组
        while(p < m || q < r){
            if(q >= r || p < m && nums[p] <= nums[q]){
                count += (q - m);
                tmp[k++] = nums[p++];
            }
            else tmp[k++] = nums[q++];
        }
        for(int k = l; k<r; k++){
            nums[k] = tmp[k];
        }
        return (count % 1000000007);
    }
    
    public:
    int InversePairs(vector<int> data){
        vector<int> tmp(data.size());
        return merge_sort(data, 0, data.size(), tmp) ;
    }
};

发表于 2021-10-16 22:41:34 回复(0)

输入描述:

输入

输出

输入

输出

python 归并排序

问题信息

热门推荐

通过挑战的用户

相关试题