牛客题解官

2022-04-22 11:41 清华大学 Java

关注

题解 | #数组中的逆序对#

数组中的逆序对

http://www.nowcoder.com/practice/96bd6684e04a44eb80e6a68efc0ec6c5

题目的主要信息：

在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。
输入一个数组，求一个数组的全部逆序对，答案对1000000007取模
保证输入的数组中没有的相同的数字

举一反三：

学习完本题的思路你可以解决如下题目：

BM.12 单链表的排序

BM.5 合并k个已排序的链表

方法一：归并排序(推荐使用)

知识点：分治

分治即“分而治之”，“分”指的是将一个大而复杂的问题划分成多个性质相同但是规模更小的子问题，子问题继续按照这样划分，直到问题可以被轻易解决；“治”指的是将子问题单独进行处理。经过分治后的子问题，需要将解进行合并才能得到原问题的解，因此整个分治过程经常用递归来实现。

思路：

因为我们在归并排序过程中会将数组划分成最小为1个元素的子数组，然后依次比较子数组的每个元素的大小，依次取出较小的一个合并成大的子数组。

//取中间
int mid = (left + right) / 2; 
//左右划分合并
merge(divide(left, mid, data, temp), divide(mid + 1, right, data, temp));

这里我们也可以用相同的方法划分，划分之后相邻一个元素的子数组就可以根据大小统计逆序对，而不断往上合并的时候，因为已经排好序了，我们逆序对可以往上累计。我们主要有以下三个阶段。

具体做法：

step 1：划分阶段：将待划分区间从中点划分成两部分，两部分进入递归继续划分，直到子数组长度为1.
step 2：排序阶段：使用归并排序递归地处理子序列，同时统计逆序对，因为在归并排序中，我们会依次比较相邻两组子数组各个元素的大小，并累计遇到的逆序情况。而对排好序的两组，右边大于左边时，它大于了左边的所有子序列，基于这个性质我们可以不用每次加1来统计，减少运算次数。
step 3：合并阶段：将排好序的子序列合并，同时累加逆序对。

图示：

alt

Java实现代码：

public class Solution {
    public int mod = 1000000007;
    public int mergeSort(int left, int right, int [] data, int [] temp){
        //停止划分
        if(left >= right)    
            return 0;
        //取中间
        int mid = (left + right) / 2; 
        //左右划分合并
        int res = mergeSort(left, mid, data, temp) + mergeSort(mid + 1, right, data, temp); 
        //防止溢出
        res %= mod;  
        int i = left, j = mid + 1;
        for(int k = left; k <= right; k++)
            temp[k] = data[k];
        for(int k = left; k <= right; k++){
            if(i == mid + 1)
                data[k] = temp[j++];
            else if(j == right + 1 || temp[i] <= temp[j])
                data[k] = temp[i++];
            //左边比右边大，答案增加
            else{ 
                data[k] = temp[j++];
                // 统计逆序对
                res += mid - i + 1; 
            }
        }
        return res % mod;
    }
    public int InversePairs(int [] array) {
        int n = array.length;
        int[] res = new int[n];
        return mergeSort(0, n - 1, array, res);
    }
}

C++实现代码：

class Solution {
public:
    int mod = 1000000007;
    int mergeSort(int left, int right, vector<int>& data, vector<int>& temp){
        //停止划分
        if(left >= right)    
            return 0;
        //取中间
        int mid = (left + right) / 2; 
        //左右划分合并
        int res = mergeSort(left, mid, data, temp) + mergeSort(mid + 1, right, data, temp); 
        //防止溢出
        res %= mod;  
        int i = left, j = mid + 1;
        for(int k = left; k <= right; k++)
            temp[k] = data[k];
        for(int k = left; k <= right; k++){
            if(i == mid + 1)
                data[k] = temp[j++];
            else if(j == right + 1 || temp[i] <= temp[j])
                data[k] = temp[i++];
            //左边比右边大，答案增加
            else{ 
                data[k] = temp[j++];
                //统计逆序对
                res += mid - i + 1; 
            }
        }
        return res % mod;
    }
    int InversePairs(vector<int> data) {
        int n = data.size();
        vector<int> res(n);
        return mergeSort(0, n - 1, data, res);
    }
};

Python实现代码

class Solution:
    mod = 1000000007
    def MergeSort(self, left: int, right: int, data: List[int], temp: List[int]) -> int:
         # 停止划分
        if left >= right:
            return 0
        # 取中间
        mid = int((left + right) / 2) 
        # 左右划分合并
        res = self.MergeSort(left, mid, data, temp) + self.MergeSort(mid + 1, right, data, temp) 
        # 防止溢出
        res %= self.mod 
        i, j = left, mid + 1
        for k in range(left, right+1):
            temp[k] = data[k]
        for k in range(left, right+1):
            if i == mid + 1:
                data[k] = temp[j]
                j += 1
            elif j == right + 1 or temp[i] <= temp[j]:
                data[k] = temp[i]
                i += 1
            # 左边比右边大，答案增加
            else: 
                data[k] = temp[j]
                j += 1
                # 统计逆序对
                res += mid - i + 1 
        return res % self.mod
            
    def InversePairs(self , data: List[int]) -> int:
        n = len(data)
        res = [0 for i in range(n)]
        return self.MergeSort(0, n - 1, data, res)

复杂度分析：

时间复杂度： $O (n l o g_{2} n)$ ，归并排序利用分治思想，树型递归每次二分，总共能分为 $l o g_{2} n$ 层，每层合并都需要遍历数组所有元素即 $O (n)$
空间复杂度： $O (n)$ ，辅助数组temp长度为 $n$ 及递归栈最大深度不会超过 $n$

方法二：树状数组（扩展思路）

思路：

我们在统计逆序的时候，使用方法一的归并思想，就是利用排序好的部分直接获取逆序个数，而不是一个一个地比较，这样就像是把前面逆序对的个数累加起来，与前缀和类似。

而树状数组是如图所示的数组，它正好可以累加前缀和。

alt

比如4统计123的前缀和，8统计1234567的前缀，而且因为是树状的，因此操作都是 $O (l o g_{2} n)$ 。

具体做法：

step 1：首先利用一个辅助数组，复制原数组然后排序，得到一个有序序列。
step 2：然后对原数组进行离散化操作，利用二分查找映射，将数字变成其在有序数组中的位置，即数组[1 5000 2 400 30] 映射为 ——> [1 5 2 4 3]，这样我们能根据这个数字在有序数组中的位置和实际位置判断它前面有多少是逆序的，同时不必开辟数字原本大小的空间，减少空间需求。因为题目所给没有重复元素，因此也不用去重，还是 $n$ 个数字。
step 3：然后从前往后遍历每个元素，查找在树状数组中的前缀和，表示这个元素在树状数组中出现过多少，前缀和做差，表示值在 $[a r r a y [i] + 1, n]$ 中出现的次数，也就是逆序数个数。

Java实现代码：

import java.util.*;
class BIT {
    private int[] tree;
    private int n;
    //初始化树状数组的大小
    public BIT(int m) { 
        this.n = m;
        this.tree = new int[m + 1];
    }
    //使数组呈现2、4、8、16这种树状
    public int lowbit(int x) { 
        return x & (-x);
    }
    //查询序列1到x的前缀和
    public int query(int x) { 
        int res = 0;
        while(x != 0){
            res += tree[x];
            x -= lowbit(x);
        }
        return res;
    }
    //序列x位置的数加1
    public void update(int x) { 
        while(x <= n){
            tree[x]++;
            x += lowbit(x);
        }
    }
}

public class Solution {
    public int mod = 1000000007;
    public int InversePairs(int [] array) {
        int n = array.length;
        int[] temp = new int[n];
        System.arraycopy(array, 0, temp, 0, n);
        //排序得到一份有序的数组
        Arrays.sort(temp); 
        //二分法重新映射，将数字变成其在有序数组中的位置
        for (int i = 0; i < n; ++i) 
            //二分法查找在其在有序数组中的位置
            array[i] = Arrays.binarySearch(temp, array[i]) + 1;
        //建立大小为n的树状数组
        BIT bit = new BIT(n); 
        int res = 0;
        //统计逆序对
        for(int i = 0; i < n; i++){ 
            //前缀和做差
            res = (res + bit.query(n) - bit.query(array[i])) % mod;
            bit.update(array[i]);
        }
        return res;
    }
}

C++实现代码：

class BIT {
private:
    vector<int> tree;
    int n;
    
public:
    //初始化树状数组的大小
    BIT(int m) : n(m), tree(m + 1) {} 
    //使数组呈现2、4、8、16这种树状
    int lowbit(int x){ 
        return x & (-x);
    }
    //查询序列1到x的前缀和
    int query(int x){ 
        int res = 0;
        while(x){
            res += tree[x];
            x -= lowbit(x);
        }
        return res;
    }
    //序列x位置的数加1
    void update(int x){ 
        while(x <= n){
            tree[x]++;
            x += lowbit(x);
        }
    }
};
class Solution {
public:
    int mod = 1000000007;
    int InversePairs(vector<int> data) {
        int n = data.size();
        int res = 0;
        vector<int> temp = data;
        //排序得到一份有序的数组
        sort(temp.begin(), temp.end());
        //二分法重新映射，将数字变成其在有序数组中的位置
        for(int i = 0; i < n; i++) 
            //二分法查找在其在有序数组中的位置
            data[i] = lower_bound(temp.begin(), temp.end(), data[i]) - temp.begin() + 1;
        //建立大小为n的树状数组
        BIT bit(n); 
        //统计逆序对
        for(int i = 0; i < n; i++){ 
            //前缀和做差
            res = (res + bit.query(n) - bit.query(data[i])) % mod;
            bit.update(data[i]);
        }
        return res;
    }
};

Python实现代码：

import copy
#二分查找函数
def binarySearch (arr, l, r, x): 
    if r >= l: 
        mid = int(l + (r - l) / 2)
        if arr[mid] == x: 
            return mid 
        elif arr[mid] > x: 
            return binarySearch(arr, l, mid - 1, x) 
        else: 
            return binarySearch(arr, mid + 1, r, x) 
    else: 
        return -1
    
class BIT:
    m = 0
    tree = []
    
    # 初始化
    def __init__(self, m: int): 
        self.n = m
        self.tree = [0 for i in range(m + 1)]
    
    # 使数组呈现2、4、8、16这种树状
    def lowbit(self, x: int) -> int: 
        return x & (-x)
    
    # 查询序列1到x的前缀和
    def query(self, x: int) -> int: 
        res = 0
        while x:
            res += self.tree[x]
            x -= self.lowbit(x)
        return res
    #序列x位置的数加1
    def update(self, x: int):
        while x <= self.n:
            self.tree[x] += 1
            x += self.lowbit(x)
            
class Solution:
    mod = 1000000007
    def InversePairs(self , data: List[int]) -> int:
        n = len(data)
        temp = copy.deepcopy(data)
        #排序得到一份有序的数组
        temp.sort()
        #二分法重新映射，将数字变成其在有序数组中的位置
        for i in range(n): 
            #二分法查找在其在有序数组中的位置
            data[i] = binarySearch(temp, 0, len(temp), data[i]) + 1
        #建立大小为n的树状数组
        bit = BIT(n) 
        res = 0
        #统计逆序对
        for i in range(n): 
            #前缀和做差
            res = (res + bit.query(n) - bit.query(data[i])) % self.mod
            bit.update(data[i])
        return res

复杂度分析：

时间复杂度： $O (n l o g_{2} n)$ ，sort函数排序为 $O (n l o g_{2} n)$ ，离散化过程中一共 $n$ 次二分法时间复杂度为 $O (l o g_{2} n)$ ，一共 $n$ 次，统计逆序对过程中，查询更新都是 $O (l o g_{2} n)$ ，一共 $n$ 次
空间复杂度： $O (n)$ ，辅助数组temp的长度和树状数组的长度都是 $n$

全部评论

推荐最新楼层

小王爱吃酒心荷包蛋

上海海事大学 C++

不理解，中间进行 //防止溢出 res %= mod; 可以举个例子吗

1 回复分享

发布于 2023-04-19 11:13 上海

练习时长两年半的太平湖水怪很理智

清华大学 Java

看不懂代码，递归连个注释都没有

1 回复分享

发布于 2023-09-27 15:36 广东

有pp才有真相

成都体育学院 Java

合并排序里面，这里代码很精简 for(int k = left; k <= right; k++){ if(i == mid + 1) data[k] = temp[j++]; else if(j == right + 1 || temp[i] <= temp[j]) data[k] = temp[i++];

点赞回复分享

发布于 2022-07-14 07:34

倾闻香来

攀枝花学院 C++

官方两种方式的方法各自优缺点是啥?

点赞回复分享

发布于 2022-10-05 11:13 四川

睡着了别醒

门头沟学院车联网功能架构工程师

请问这句话何解呀：“而对排好序的两组，右边大于左边时，它大于了左边的所有子序列” 不应该是排好序的两个数组，右边小于左边时，它小于左边的所有子序列吗

点赞回复分享

发布于 2023-03-15 09:52 湖北

不讲武德的太平湖水怪很喜欢吃火锅

New York University Python

public class Solution { // 模数，用于防止溢出 public int mod = 1000000007; /** * 归并排序的变种，既排序数组也计算逆序对 * @param left 区间左端点 * @param right 区间右端点 * @param data 原数组 * @param temp 临时数组 * @return 逆序对数量 */ public int mergeSort(int left, int right, int [] data, int [] temp) { // 如果左端点大于或等于右端点，说明只有一个元素或没有元素，直接返回0 if (left >= right) return 0; // 计算区间中间位置 int mid = (left + right) / 2; // 递归地对左半部分和右半部分分别进行排序，并加上各自的逆序对数量 int res = mergeSort(left, mid, data, temp) + mergeSort(mid + 1, right, data, temp); // 防止res超出int的范围 res %= mod; // 初始化左右部分的起始指针 int i = left, j = mid + 1; // 将当前区间的数据复制到临时数组 for(int k = left; k <= right; k++) temp[k] = data[k]; // 对当前区间进行归并操作 for(int k = left; k <= right; k++) { // 如果左半部分已经完全归并，直接归并右半部分 if (i == mid + 1) data[k] = temp[j++]; // 如果右半部分已经完全归并，或者左半部分当前值小于等于右半部分当前值，归并左半部分 else if (j == right + 1 || temp[i] <= temp[j]) data[k] = temp[i++]; // 否则，存在逆序对，归并右半部分，并统计逆序对数量 else { data[k] = temp[j++]; // 添加逆序对数量 res += mid - i + 1; } } // 返回当前区间的逆序对数量 return res % mod; } /** * 计算数组中的逆序对数量 * @param array 输入数组 * @return 逆序对数量 */ public int InversePairs(int [] array) { int n = array.length; int[] res = new int[n]; // 创建临时数组 // 对整个数组进行归并排序并计算逆序对数量 return mergeSort(0, n - 1, array, res); } }

点赞回复分享

发布于 2023-09-10 01:11 美国