【牛客】BM20数组中的逆序对

AI摘要：

BM20 数组中的逆序对

中等 通过率：16.61% 时间限制：3秒 空间限制：256M
知识点数组

描述

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

数据范围： 对于 50% 的数据, size≤104
对于 100% 的数据, size≤105
数组中所有数字的值满足 0≤val≤109

要求：空间复杂度 O(n)，时间复杂度 O(nlogn)

输入描述：

题目保证输入的数组中没有的相同的数字

示例1

1
2
输入：[1,2,3,4,5,6,7,0]
返回值：7

示例2

1
2
输入：[1,2,3]
返回值：0

题解

暴力方法：

按住一个arr[i], 依次判断{i+1 … n-1]是否满足条件。n为数组的大小，对于10^5数据，O(N^2)算法显然超时。

归并排序思想：

可以参考：排序——归并排序（Merge sort）-CSDN博客

归并排序的过程，主要有以下两个操作：

  • 递归划分整个区间为基本相等的左右两个区间
  • 合并两个有序区间

主函数

1
2
3
4
5
6
7
8
9
10
11
12
13
/* 
     * @param nums int整型vector 
     * @return int整型
     */
int InversePairs(vector<int>& nums) {
    // 创建记录逆序数的变量
    int ret = 0;
    // 直接在最外层开辟一个足够大的临时数组，然后传引用到函数
    vector<int> tmp(nums.size());

    mergeSort(nums, tmp, 0, nums.size()-1, ret);
    return ret;
}

递归划分整个区间

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
 /**
     * @param arr vector<int>原数组
     * @param tmp vector<int>临时数组 
     * @param l int整型 左端点 
     * @param r int整型 右端点
     * @param ret int整型 逆序对计数
     */
void mergeSort(vector<int> &arr, vector<int> &tmp, int l, int r, int& ret){
    // 递归结束条件
    if(l >= r){
        return;
    }
	
    // 一分为二
    int mid = l + ((r - l) >> 1);
    // 左半部分数组排序
    mergeSort(arr, tmp, l, mid, ret);
    // 右半部分数组排序
    mergeSort(arr, tmp, mid+1, r, ret);
    // 将排序好的左右数组合并排序
    merge(arr, tmp, l, mid, r, ret);
}

合并两个有序区间

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
void merge(vector<int> &arr, vector<int> &tmp, int l, int mid, int r, int& ret){
    int i = l, j = mid + 1, k = 0;
    
    // 左右数组同时遍历，按大小加入临时数组
    while(i <= mid && j <= r){
        if(arr[i] > arr[j]){
            //左数组的元素比右数组大，因为左右数组各自已经排序
            //此时可知这段数组存在(mid + 1 - i)个逆序对
            ret += (mid + 1 - i);
            ret %= kmod;
            tmp[k++] = arr[j++];
        }else{
            tmp[k++] = arr[i++];
        }
    }

    // 存入剩下的数组元素
    while(i <= mid){
        tmp[k++] = arr[i++];
    }
    while(j <= r){
        tmp[k++] = arr[j++];
    }

    //临时数组拷贝回原数组，完成排序
    for(k = 0, i = l; i <= r; i++, k++){
        arr[i] = tmp[k];
    }
}

时间复杂度：O(NlogN)
空间复杂度：O(N)

学习笔记 > 算法
#算法 #牛客网 #排序
【牛客】BM20数组中的逆序对
https://blog.cngo.rr.nu/posts/7360.html
作者
cngo
发布于
2024年8月13日
许可协议