Acwing基础课每日一题 第四天 788-简单-逆序对的数量

Acwing基础课每日一题 第四天 788-简单-逆序对的数量 文章目录

前言

题目描述

思路解析：

代码（c++）

结语

---

原题连接：788-简单-逆序对的数量

前言

算法是考研和实习找工作进大厂的必备工具，为了23考研以及日后进大厂，开始学习算法！

作者简介

大家好，我是977，一个正在慢慢进步的程序猿小白，很高兴能在这里遇见大家，每天一点点成长，一起早日成为大佬！！！

算法基础课共106题

这是我的第4/106题

题目描述

给定一个长度为 n 的整数数列，请你计算数列中的逆序对的数量。

逆序对的定义如下：对于数列的第 i 个和第 j 个元素，如果满足 ia[j]，则其为一个逆序对；否则不是。

输入格式

第一行包含整数 n，表示数列的长度。

第二行包含 n 个整数，表示整个数列。

输出格式

输出一个整数，表示逆序对的个数

数据范围

1≤n≤100000

数列中的元素的取值范围 [1,]。

输入样例

6
2 3 4 5 6 1

输入样例

5

思路解析：

算法：归并排序 （ MergeSort ）

时间复杂度：O(nlog(n))

解题思路：

1.把数组分成某个位置分成两个数组
2.对两边递归排序并计算出在同一边逆序对的数量
3.归并数组，并计算不在同一边的逆序对的数量
4.然后遍历看看有没有没归并的数
5.然后赋值给原数组

代码（c++）

#include
using namespace std;

const int N = 100010;

int n;
int q[N],tem[N];

long long merge_sort(int q[],int l,int r){
    if(l >= r) return 0;
    
    int mid = (l + r) >> 1;
    //递归左右两边逆序数对
    long long res = merge_sort(q,l,mid) + merge_sort(q,mid + 1,r);
    
    //归并并计算不在一边的逆序数对
    int k = 0,i = l,j = mid + 1;
    while(i <= mid && j <= r)
        if(q[i] <= q[j]) tem[k++] = q[i++];
        else {
            tem[k++] = q[j++];
            res += mid - i + 1;//计算逆序对数        
            
        }
    //扫尾
    while (i <= mid) tem[k++] = q[i++];
    while (j <= r) tem[k++] = q[j++];
    
    //赋给原数组
    for (int i = l,j = 0; i <= r; i ++ ,j++)
        q[i] = tem[j];
        
        return res;
}

int main()
{
    scanf("%d", &n);
    for (int i = 0; i < n; i ++ ) scanf("%d", &q[i]);
    printf("%ld",merge_sort(q,0,n - 1));
    
    return 0;
}

结语

学习贵在坚持，Acwing算法基础课，每日一题

期待各位的关注和监督