数组中的逆序对_

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

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)

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++

迷茫的他在努力存钱

//思路：分治的思想。
//在合并有序数组时，当左边数组的指针移动至下一元素时，说明该指针的元素能够和右指针元素之前的所有元素构成逆序对关系。
//所以逆序对总数加上右边指针前的元素个数。
//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)

C++

ouluy

坑点1：因为没有说数组里值的大小范围属于0~n-1，所以离散化，把数据变成1~n范围

然后用树状数组求逆序对

class Solution {
public:
    #define ll long long
    #define mod 1000000007
    #define N 100010
    int lowbit(int i){
        return i&(-i);
    }
    void add(int i,int x){
        while(i<=n){
            c[i]+=x;
            i+=lowbit(i);
        }
        return ;
    }
    int getsum(int i){
        int sum=0;
        while(i>0){
            sum+=c[i];
            i-=lowbit(i);
        }
        return sum;
    }
    int InversePairs(vector<int> data) {
        n=data.size();
        vector<pair<int,int> >da;
        for(int i=0;i<n;i++){
            da.push_back(make_pair(data[i],i+1));
        }
        sort(da.begin(),da.end());
        for(int i=0;i<n;i++){
            hash[da[i].second]=i+1;
        }
        ll ans=0;
        for(int i=1;i<=n;i++){
             add(hash[i],1);
             ans+=(ll)i-getsum(hash[i]);
             ans%=mod;
        }
        return ans;
    }
private:
    int c[N];
    int hash[N];
    int n;
};

发表于 2021-08-03 20:46:26 回复(0)

JavaScript

祝啊霸

提供一个JS的可读性最好的解法（效率击败90%的解法）： Code is the best note

function InversePairs(data)
{
    let count = 0
    if (!Array.isArray(data) || data.length < 2){
        return count
    }

    // 以下两个箭头函数构成一个归并排序
    const merge = (left, right) => {
        const arr = []
        while (left.length && right.length) {
            if (left[0] > right[0]) {
                arr.push(right.shift())
                count += left.length
            } else {
                arr.push(left.shift())
            }
        }
        left.length && arr.push(...left)
        right.length && arr.push(...right)
        return arr
    }

    const mergeSort = (arr) => {
        if (arr.length < 2) {
            return arr
        }
        const middle = Math.ceil(arr.length / 2)
        const leftPart = arr.slice(0, middle)
        const rightPart = arr.slice(middle)
        return merge(mergeSort(leftPart), mergeSort(rightPart))
    }

    mergeSort(data)
    return count % 1000000007
}

编辑于 2021-06-23 22:56:09 回复(0)

C/C++

xidian_mao

树状数组非常优美的结构

void add(int* tree, int k, int n) {
    while(k<=n) {
        tree[k] += 1;
        k += k&(-k);
    }
}

long long sum_tree(int* tree, int k) {
    long long ans = 0; 
    while(k) {
        ans += tree[k];
        k -= k&(-k);
    }
    return ans;
}

class Solution {
public:
    int InversePairs(vector<int> data) {
        int n = data.size();
        vector<int> a = data;
        sort(a.begin(), a.end());
        int cnt = 0;
        for(int i=1; i<n; i++) 
            if(a[i] != a[cnt])
                a[++cnt] = a[i];
        int tree[cnt+7];
        memset(tree, 0, sizeof(tree));
        long long ans = 0;
        for(int i=0; i<n; i++) {
            int id = lower_bound(a.begin(),a.end(), data[i]) - a.begin() + 1;
            ans = (ans + sum_tree(tree,  cnt+1) - sum_tree(tree,  id)) % mod;
            add(tree, id, cnt+1);
        }
        return ans;
    }
    
    const long long mod = 1e9 + 7;
};

发表于 2021-05-27 15:43:19 回复(0)

C/C++

木析

class Solution {
public:
    int InversePairs(vector<int> data) {
        return merge(data,0,data.size()-1);
    }
    int merge(vector<int>& data, int left,int right) {
        if(left==right) {
            return 0; //只有一个数，不存在逆序对
        }
        vector<int> tem;
        int mid=left+((right-left)>>1);
        long long x=merge(data,left,mid);
        x+=merge(data,mid+1,right);
        int i=left,j=mid+1;
        while(i<=mid && j<=right) {
            if(data[i]>data[j]) {
                x+=(mid-i+1); //逆序对
                tem.push_back(data[j++]);
            } else{
                tem.push_back(data[i++]);
            }
        }
        while(i<=mid) {
            tem.push_back(data[i++]);
        }
        while(j<=right) {
            tem.push_back(data[j++]);
        }
//         copy(data.begin()+mid+1,data.begin()+right+1,tem);
        for(int i=left;i<=right;i++) {
            data[i]=tem[i-left];
        }
        return x%1000000007;
    }
};

发表于 2021-04-23 15:04:27 回复(0)

Python

zhd要到160斤

# -*- coding:utf-8 -*-
class Solution:
    #用来定义一个count，就可以不断的在原来基础上叠加了
    def __init__(self):
        self.count = 0
    def InversePairs(self, data):
        # write code here
        #这个是用来合的函数，返回res，只是在合的过程中可以用来计算count
        def merge(s1, s2):
            res = []
            i = j = 0
            n = len(s1)
            m = len(s2)
            while i < n and j < m:
                if s1[i] > s2[j]:
                    self.count += n - i
                    res.append(s2[j])
                    j += 1
                else:
                    res.append(s1[i])
                    i += 1
            res += s1[i:] if i < n else s2[j:]
            return res
        #这个是用来分的函数，就是一直分分分，直到列表中只剩下1个
        def merge_sort(li):
            if len(li) == 1:
                return li
            if len(li)<1:
                return []
            mid = len(li)//2
            lt = merge_sort(li[:mid])
            rt = merge_sort(li[mid:])
            return merge(lt, rt)
        #就是用来merge后看看count多少，最后返回一下就行了
        if len(data) < 2:
            return 0
        merge_sort(data)
        return self.count%1000000007

分治法，归并排序，好处是比较一下就可以输出好多不重复的答案

发表于 2020-11-29 10:19:46 回复(1)

Java

诗酒趁年华丶

刚刚做题的时候发现Scanner的输入效率比BufferedReader低了整整100ms……平时没注意这些，想着Scanner用着很方便，以后可以稍微留意一下。

发表于 2020-09-10 20:49:28 回复(0)

何之洲是网名不是真名

有些比较高赞的回答可能年代比较久远，现在新增了一些卡时间和空间的测试用例，如果你确定代码逻辑（特指用归并思想解题）上没问题，可以试试：

1. 在正确的位置mod 1000000007了吗？

2. 记录cnt的类型从int改成long，虽然32位的int能表示1000000007，但是不确保被模数不溢出。

3. 临时数组不要多次分配和释放，即不要在每次merge的时候建立临时数组（堆区和栈区都不行），而是应该作为参数传递（指针或引用）给merge，并且最好整个程序周期都用同一个临时数组。

附上我自己的，可能过段时间又不能ac了：

class Solution {
public:
    void copy(vector<int> &dst, vector<int> &src, int l, int r) {
        while (l <= r) {
            dst[l] = src[l];
            l++;
        }
    }
    
    long merge(vector<int> &data, vector<int> &tmp, int l, int m, int r) {
        int i = l, j = m + 1, k = l;
        long ret = 0;
        while (i <= m && j <= r) {
            if (data[i] <= data[j]) {
                tmp[k++] = data[i++];
            } else {
                tmp[k++] = data[j++];
                ret += (m - i + 1);
            }
        }
        while (i <= m) {
            tmp[k++] = data[i++];
        }
        while (j <= r) {
            tmp[k++] = data[j++];
        }
        return ret;
    }
    
    long mergesort(vector<int> &data, vector<int> &tmp, int l, int r) {
        long left = 0, right = 0, cnt = 0;
        if (l < r) {
            int m = (l + r) / 2;
            left = mergesort(data, tmp, l, m) % 1000000007;
            right = mergesort(data, tmp, m+1, r) % 1000000007;
            cnt = merge(data, tmp, l, m, r) % 1000000007;
            copy(data, tmp, l, r);
        }
        return (left + right + cnt) % 1000000007;
    }

    int InversePairs(vector<int> data) {
        vector<int> tmp(data.size());
        return mergesort(data, tmp, 0, data.size()-1);
    }
};

编辑于 2020-08-25 14:39:19 回复(0)

Java

花言不知梦

import java.util.Arrays;
public class Solution {
    // 采用归并排序
    public int InversePairs(int[] array){
        int len = array.length;
        if(array == null || len == 0)
            return 0;
        int[] copy = array.clone();
        return InversePairs(copy, 0, len - 1);
    }

    public int InversePairs(int[] copy, int begin, int end){
        if(begin == end)
            return 0;
        int mid = (begin + end) >> 1;
        int leftCnt  = InversePairs(copy, begin, mid) % 1000000007;
        int rightCnt = InversePairs(copy, mid + 1, end) % 1000000007;
        int cnt = 0;
        int i = mid;
        int j = end;
        while(i >= begin && j > mid){
            if(copy[i] > copy[j]){
                cnt += (j - mid);
                if(cnt >= 1000000007)
                    cnt = cnt % 1000000007;
                i--;
            }else
                j--;
        }
        Arrays.sort(copy, begin, end + 1);
        return (leftCnt + rightCnt + cnt) % 1000000007;
    }
    
}

发表于 2020-08-03 19:02:22 回复(1)

敲多码代

class Solution 
{
public:
    long long num=0;//逆序次数
    //归并操作，一边归并，一边统计逆序次数
    //归并 [left,mid]和（mid,right]
    int InversePairs(vector<int> data) 
    {
        //使用归并排序的思想
        vector<int> temp(data.size());//创建一个临时数组，只用创建一次，避免多次创建
        sort(data,0,data.size()-1,temp);
        return num%=1000000007;
    }

    //归并排序
    void sort(vector<int>& data,int left,int right,vector<int>& temp)
    {
        if(left<right)
        {
            int mid=left+((right-left)>>1);
            sort(data,left,mid,temp);
            sort(data,mid+1,right,temp);
            mergeVec(data,left,mid,right, temp);
        }
    }
    //归并操作
    void mergeVec(vector<int>& data,int left,int mid,int right,vector<int>& temp )
    {
        int l1=left;
        int l2=mid+1;
        int index=left;
        while(l1<=mid&&l2<=right)
        {
            if(data[l1]<=data[l2])
                temp[index++]=data[l1++];
            else//逆序了
            {
                temp[index++]=data[l2++];
                //下面这两行是相对于归并排序增加的两行，如果只是归并排序，不要下面这两行就可以了
                num+=mid-l1+1;//data[l1]一直到data[mid]都大于data[l2]，就存在mid-l1+1对逆序对
                num%=1000000007;
            }
        }
        while(l1<=mid)
            temp[index++]=data[l1++];
        while(l2<=right)
            temp[index++]=data[l2++];
        for(int i=left;i<=right;i++)
            data[i]=temp[i];
    }
};

发表于 2020-06-14 22:07:33 回复(0)

C/C++

black_mamba

class Solution {
public:
    int count=0;
    void Merge(vector<int> &data,int l,int m,int r)
    {
        vector<int> temp;
        int i=l;
        int j=m+1;
        while(i<=m && j<=r)
        {
            if(data[i]>data[j])
            {
                count=count+m-i+1;
                temp.push_back(data[j++]);
            }
            else
            {
                temp.push_back(data[i++]);
            }
        }
        while(i<=m)
        {
            temp.push_back(data[i++]);
        }
        while(j<=r)
        {
            temp.push_back(data[j++]);
        }
        
        for(int i=0;i<temp.size();++i)
        {
            data[i+l]=temp[i];
        }
    }
    void Merge_sort(vector<int> &data,int l,int r)
    {
        if(l<r)
        {
            int m=(r-l)/2+l;
            Merge_sort(data,l,m);
            Merge_sort(data,m+1,r);
            
            Merge(data,l,m,r);
        }
        
    }
    int InversePairs(vector<int> data) {
        if(!data.size())
        {
            return 0;
        }
        Merge_sort(data,0,data.size()-1);
        return (count%1000000007);
    }
};

归并排序，分治成单个子序列，再归并排序的同时统计逆序对。

编辑于 2020-05-30 10:21:05 回复(0)

晚睡晚起写bug

归并排序的同时统计逆序对的数量。

public class Solution {
    private static long sum = 0;
    public int InversePairs(int [] array) {
        int len = array.length;
        int l = 0;
        int r = len - 1;
        divide(l, r, array);
        return (int) (sum % 1000000007);
    }
    private void divide(int l, int r, int[] array) {
        if (l == r) return;
        if (l != r) {
            int mid = (l + r) >> 1;
            divide(l, mid, array);
            divide(mid + 1, r, array);
            merge(l, mid, r, array);
        }
    }
    private void merge(int l, int mid, int r, int[] array) {
        int i = l;//左区间起点
        int j = mid + 1;//右区间起点
        int[] temp = new int[r - l + 1];
        int idx = 0;
        while (i <= mid && j <= r) {
            if (array[i] > array[j]) {
                sum += mid - i + 1;//更新逆序对数量
                temp[idx] = array[j];
                ++idx;
                ++j;
            } else {
                temp[idx] = array[i];
                ++idx;
                ++i;
            }
        }
        while (i <= mid) {
            temp[idx] = array[i];
            ++idx;
            ++i;
        }
        while (j <= r) {
            temp[idx] = array[j];
            ++idx;
            ++j;
        }
        idx = 0;
        for (int k = l; k <= r; k++) {
            array[k] = temp[idx];
            ++idx;
        }
    }
}

发表于 2020-05-17 20:48:20 回复(0)

牛客687675237号

说实话我还没看懂这道题的意思，谁能讲解一下

发表于 2020-04-26 14:27:16 回复(0)

C/C++

翰轩阳

/*使用归并排序思想*/

class Solution {

public:
int InversePairs(vector<int> arr) {
if (arr.size() < 2)
return 0;
long long res = 0;
res = mergeSort(arr, 0, arr.size() - 1);
return res%1000000007;
}
long long mergeSort(vector<int>& arr, int left, int right)
{
if (left == right)
return 0;
long long res = 0;

int mid = left + ((right-left) >> 1);

//左侧归并时求得的逆序对个数+右侧归并时求得的逆序对个数+整体归并时求得的逆序对个数

res = mergeSort(arr, left, mid)+mergeSort(arr, mid + 1, right)+merge(arr, left, mid, right);
return res;
}
long long merge(vector<int>& arr, int left, int mid, int right)
{
vector<int> help(right-left+1);
int p1 = left;
int p2 = mid+1;
int i = 0;
long long res = 0;
while (p1 <= mid && p2 <= right)

{

//左侧>右侧时，左侧到中间的元素均>右侧，逆序对为mid-p1+1

res += arr[p1] > arr[p2] ? mid-p1+1 : 0;
help[i++] = arr[p1] < arr[p2] ? arr[p1++] : arr[p2++];
}
while (p1 <= mid)
{
help[i++] = arr[p1++];
}
while (p2 <= right)
{
help[i++] = arr[p2++];
}
for (i = 0; i < help.size(); i++)
{
arr[left+i] = help[i];
}
return res;

}

};

/*归并排序代码*/

void mergeSort(vector<int>& arr, int left, int right)
{
if (left == right)
return;
int mid = left + ((right-left) >> 1);
mergeSort(arr, left, mid);
mergeSort(arr, mid + 1, right);
merge(arr, left, mid, right);
}
void merge(vector<int>& arr, int left, int mid, int right)
{
vector<int> help(right-left+1);
int p1 = left;
int p2 = mid+1;
int i = 0;

while (p1 <= mid && p2 <= right)
{
help[i++] = arr[p1] < arr[p2] ? arr[p1++] : arr[p2++];
}
while (p1 <= mid)
{
help[i++] = arr[p1++];
}
while (p2 <= right)
{
help[i++] = arr[p2++];
}
for (i = 0; i < help.size(); i++)
{
arr[left+i] = help[i];
}
}
/*求小和代码*/

/*使用归并排序思想*/

class Solution {

public:
int InversePairs(vector<int> arr) {
if (arr.size() < 2)
return 0;
long long res = 0;
res = mergeSort(arr, 0, arr.size() - 1);
return res%1000000007;
}
long long mergeSort(vector<int>& arr, int left, int right)
{
if (left == right)
return 0;
long long res = 0;

int mid = left + ((right-left) >> 1);

//左侧归并时求得的小和+右侧归并时求得的小和+整体归并时求得的小和

res = mergeSort(arr, left, mid)+mergeSort(arr, mid + 1, right)+merge(arr, left, mid, right);
return res;
}
long long merge(vector<int>& arr, int left, int mid, int right)
{
vector<int> help(right-left+1);
int p1 = left;
int p2 = mid+1;
int i = 0;
long long res = 0;
while (p1 <= mid && p2 <= right)

{

//左侧<右侧时，小和为左侧的值*（中间到右侧的所有个数）

res += arr[p1] < arr[p2] ? (r - p2 + 1) * arr[p1] : 0;
help[i++] = arr[p1] < arr[p2] ? arr[p1++] : arr[p2++];
}
while (p1 <= mid)
{
help[i++] = arr[p1++];
}
while (p2 <= right)
{
help[i++] = arr[p2++];
}
for (i = 0; i < help.size(); i++)
{
arr[left+i] = help[i];
}
return res;

}

};

编辑于 2020-04-25 21:38:03 回复(0)

Java

Kinggj

期初一看题目觉得很简单，就暴力解决，然而没有考虑空间和时间等问题不满足要求；

最后还是借鉴大佬的做法使用归并排序（有递归dp的思想，顺带也复习了一波归并排序）；

在比较的时候就不用重复比较；时间复杂度O（o*logN）;

public class Solution {
    int th;//利用归并排序 O(o*logn)
    public int InversePairs(int [] array) {
        mergeSort(array,0,array.length-1);
        return th;
    }
    public void mergeSort(int[] array, int start, int end){
        if(start>=end) return;
        int mid = (start+end)/2;
        mergeSort(array,start,mid);
        mergeSort(array,mid+1,end);
        mergeOne(array,start,mid,end);
    }
    public void mergeOne(int[] array, int start,int mid,int end){
        int[] tmp = new int[end-start+1];
        int k=0,i=start,j=mid+1;
        while(i<=mid && j<=end){
            if(array[i]<=array[j]){
                tmp[k++] = array[i++];
            }else{//如果前面的元素大于后面的，那么在前面元素之后的元素都能和后面的元素构成逆序对
                tmp[k++] = array[j++];
                th=(th+(mid-i+1))%1000000007;////如果前面的元素大于后面的，那么在前面元素之后的元素都能和后面的元素构成逆序对
            }
        }
        while(i<=mid) tmp[k++] = array[i++];
        while(j<=end) tmp[k++] = array[j++];
        for(int l=0;l<k;l++){
            array[start+l]=tmp[l];
        }
    }
}

发表于 2020-04-11 00:20:28 回复(0)

数组中的逆序对

输入描述:

输入

输出

输入

输出

提供一个JS的可读性最好的解法（效率击败90%的解法）： Code is the best note

问题信息

热门推荐

通过挑战的用户

相关试题