每日算法打卡:逆序对的数量 day 24

发布时间:2024年01月24日

原题链接

788. 逆序对的数量

题目难度:简单

题目描述

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

逆序对的定义如下:对于数列的第 i 个和第 j 个元素,如果满足 i < j 且 a[i] > a[j],则其为一个逆序对;否则不是。

输入格式

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

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

输出格式

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

数据范围

1 ≤ n ≤ 100000 1 \le n \le 100000 1n100000
数列中的元素的取值范围 [ 1 , 1 0 9 ] [1,10^9] [1,109]

输入样例:
6
2 3 4 5 6 1 
输出样例:
5 

题目分析

逆序对首先数对,他是一个线性代数中的概念,简单的理解就是,前面的数字比后面的数字大就是一个逆序对,需要注意的是,如果两个数字相同,则应该标记为不同的数字,只是数值相同

我们主要的思想还是采用分治,可以借用归并排序的思路,在归并排序的过程中计算出这个问题的答案

对于分治来说,如何不重不漏的将情况分出来是最重要的

屏幕截图 2024-01-24 114022.png

假设这是某一次分治的结果,分为[L,Mid]和[Mid+1,R]两个区间,红绿蓝表示可能出现的逆序对的位置

这一次分治的结果返回的是[L,R]的,所以结果应该是红色加蓝色加绿色

红色的结果是再对[L,Mid]进行归并排序的结果

绿色的结果是再对[Mid+1,R]进行归并排序的结果

那么难点就是对于蓝色的

我们假设左半边和右半边已经排号序了

此时画出图形就是这样的

屏幕截图 2024-01-24 115235.png

假设我们使用双指针,找到了一个a[j]<a[i]那么由于这两部分都是有序的,a[i]后面的所有数字都是严格大于a[j]的

通过这种方式就可以在归并的过程中计算出蓝色部分的个数了

示例代码

#include<iostream>
using namespace std;
using ll = long long;

const int N = 100010;

int n;
int a[N], tmp[N]; // tmp 存储中间结果

ll merge_sort(int l, int r)
{
    if (l >= r) return 0;
    int mid = l + r >> 1;
    ll res = merge_sort(l, mid) + merge_sort(mid + 1, r);

    int k = 0, i = l, j = mid + 1;
    while (i <= mid && j <= r)
    {
        if (a[i] <= a[j]) tmp[k++] = a[i++];
        else
        {
            tmp[k++] = a[j++];
            res += mid - i + 1;
        }
    }

    while (i <= mid) tmp[k++] = a[i++];
    while (j <= r) tmp[k++] = a[j++];

    for (i = l, j = 0; i <= r; i++, j++)
        a[i] = tmp[j];
    return res;

}

int main()
{
    cin >> n;
    for (int i = 0; i < n; i++) cin >> a[i];

    cout << merge_sort(0, n - 1) << '\n';
    return 0;
}
文章来源:https://blog.csdn.net/ye_yumo/article/details/135828922
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。