分治算法 | 归并专题

归并排序回顾

基本思想

归并排序用到了分治的思想，其基本步骤如下：

1. 分：确定分界点mid，将原排序问题分解成两个子问题left和right
2. 治：递归排序两个子问题left和right
3. 合并：将已经排好的左右区间left和right合并，得到最终排好序的结果【归并排序求解的核心】

合并过程：每次取左右区间当前最小的数进行比较，较小的数加入临时数组中。左右区间的数都遍历完毕，再将临时数组的元素按顺序拷贝回原数组。

程序代码

#include <iostream>
#include <algorithm>
using namespace std;

const int N = 100010;
int a[N], temp[N];

void mergeSort(int l, int r)
{
    if(l >= r)  return ;
    // 分
    int mid = l + r >> 1;
    // 治
    mergeSort(l, mid);
    mergeSort(mid + 1, r);
    // 合并
    int i = l, j = mid + 1, k = 0;
    // 合并结果先存在临时数组中
    while(i <= mid && j <= r) {
        if(a[i] <= a[j])  temp[k++] = a[i++];
        else  temp[k++] = a[j++];
    }
    while(i <= mid)  temp[k++] = a[i++];
    while(j <= r)  temp[k++] = a[j++];
    for(int i = l, j = 0; i <= r; i++, j++) {
        a[i] = temp[j];
    }
}

int main()
{
    int n;
    cin >> n;
    for(int i = 0; i < n; i++) {
        cin >> a[i];
    }
    mergeSort(0, n - 1);
    for(int i = 0; i < n; i++) {
        cout << a[i] << " ";
    }
    cout << endl;
    return 0;
}

复杂度分析

时间复杂度为 $O(nlogn)$ 级别

逆序对的数量

问题描述

原题链接

猫猫 TOM 和小老鼠 JERRY 最近又较量上了，但是毕竟都是成年人，他们已经不喜欢再玩那种你追我赶的游戏，现在他们喜欢玩统计。

最近，TOM 老猫查阅到一个人类称之为“逆序对”的东西，这东西是这样定义的：对于给定的一段正整数序列，逆序对就是序列中 $a_i>a_j$ 且 $i<j$ 的有序对。知道这概念后，他们就比赛谁先算出给定的一段正整数序列中逆序对的数目。注意序列中可能有重复数字。

输入格式

第一行，一个数 $n$，表示序列中有 $n$个数。

第二行 $n$ 个数，表示给定的序列。序列中每个数字不超过 $10^9$。

输出格式

输出序列中逆序对的数目。

问题分析

对于这道题，可以采用归并排序的分治思路进行求解：

• 分：将序列从中间分开，将逆序对分成三类：
  • 两个元素都在左区间
  • 两个元素都在右区间
  • 两个元素一个在左区间，一个在右区间
• 治：递归求解两个元素都在左区间的情况和两个元素都在右区间的情况。【该步骤结束后，左右区间均按照升序排序】
• 合并：i遍历左区间，j遍历右区间。若a[i] > a[j]，则说明a[i...mid]均与a[j]构成逆序对，因此逆序对个数为res += (mid - i + 1)。

程序代码

#include <iostream>
using namespace std;

typedef long long LL;

const int N = 500010;
int n;
int a[N], tmp[N];

LL mergeSort(int l, int r)
{
    if(l >= r)  return 0;
    // 分
    int mid = l + r >> 1;
    // 治：分别计算两个区间的逆序数并求和
    LL res = mergeSort(l, mid) + mergeSort(mid + 1, r);
    // 合并：计算跨区间的逆序数
    int i = l, j = mid + 1, k = 0;
    while( i <= mid && j <= r ) {
        if(a[i] <= a[j])  tmp[k++] = a[i++];
        else {
            tmp[k++] = a[j++];
            // 两个区间，与q[j]构成逆序对的个数
            res += mid - i + 1;
        }
    }
    while( i <= mid )  tmp[k++] = a[i++];
    while( j <= r )  tmp[k++] = a[j++];
    
    for(int 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 << mergeSort(0, n - 1) << endl;
    return 0;
}

复杂度分析

时间复杂度为 $O(nlogn)$ 级别

LeetCode-315. 计算右侧小于当前元素的个数

问题描述

原题链接

给你一个整数数组 nums ，按要求返回一个新数组 counts 。数组 counts 有该性质： counts[i] 的值是 nums[i] 右侧小于 nums[i] 的元素的数量。

问题分析

计算nums[i]右侧小于nums[i]的元素的数量，其实就是计算与nums[i]构成逆序对的个数。

由于需要按照原数组的顺序，返回每个元素右侧小于该元素的数量，因此可以用一个pair数据结构存储元素值和原下标。

• 分：将序列从中间分开，将逆序对分成三类：
  • 两个元素都在左区间
  • 两个元素都在右区间
  • 两个元素一个在左区间，一个在右区间
• 治：递归求解两个元素都在左区间的情况和两个元素都在右区间的情况。
• 合并：i遍历左区间，j遍历右区间，用t记录nums[i...mid] > nums[j]的对数。
  • 若nums[i] <= nums[j]，记nums[i]的原位置为pos，更新counts[pos]的值，即counts[pos] += t.
  • 若nums[i] > nums[j]，则说明 nums[i...mid]均大于nums[j] ，因此t++。

程序代码

class Solution {
private:
    void mergeSort(vector<pair<int, int>>& a, vector<int>& res, int l, int r) {
        if(l >= r)  return ;
        int mid = l + r >> 1;
        mergeSort(a, res, l, mid);
        mergeSort(a, res, mid + 1, r);
        int i = l, j = mid + 1, k = 0;
        vector<pair<int, int>> tmp(r - l + 1);
        int t = 0;
        while( i <= mid && j <= r ) {
            if(a[i].first <= a[j].first) {
                res[a[i].second] += t;
                tmp[k++] = a[i++];
            }
            else {
                t++;
                tmp[k++] = a[j++];
            }
        }
        while( i <= mid ) {
            res[a[i].second] += t;
            tmp[k++] = a[i++];
        }
        while( j <= r )  tmp[k++] = a[j++];
        for(int i = l, j = 0; i <= r; i++, j++) {
            a[i] = tmp[j];
        }
    }

public:
    vector<int> countSmaller(vector<int>& nums) {
        int n = nums.size();
        vector<pair<int, int>> a(n);
        for(int i = 0; i < n; i++) {
            a[i] = {nums[i], i};
        }
        vector<int> res(n, 0);
        mergeSort(a, res, 0, n - 1);
        return res;
    }
};

复杂度分析

时间复杂度为 $O(nlogn)$ 级别