C++实现使用分治法的思想解决寻找逆序对数量的问题

C++实现使用分治法的思想解决寻找逆序对数量的问题

题目：
给定一个长度为N的int型数组a[0, 1, 2, …, N-1]，当i < j且a[i] > a[j]，则称a[i]与a[j]是一对逆序对。求该数组的逆序对数量。

思路：
（有空再写）

代码：

//
//  main.cpp
//  InversePairNumber
//
//  Created by 胡昱 on 2021/11/1.
//

#include 
using namespace std;

// 借用归并排序算法实现分治法求数组的逆序对个数
int* computeInversePairNum(int* a, int n, int* ipn) {
    
    if (n == 1) {
        return a;
    }
    
    //  划分子问题（即划分为左右两个长度基本一致的数组）
    int leftMid = (0 + n - 1) / 2;
    int rightMid = (0 + n - 1) / 2 + 1;
    
    // 计算子问题长度
    int leftA_length = leftMid - 0 + 1;
    int rightA_length = n - rightMid;
    
    // 构建并拷贝数组
    int* leftA = new int[leftA_length];
    int* rightA = new int[rightA_length];
    for (int i = 0; i < leftA_length; ++i) {
        leftA[i] = a[i];
    }
    for (int i = leftA_length; i < n; ++i) {
        rightA[i - leftA_length] = a[i];
    }
    
    // 解决子问题（对左右两个子数组进行归并排序）
    leftA = computeInversePairNum(leftA, leftA_length, ipn);
    rightA = computeInversePairNum(rightA, rightA_length, ipn);
    
    // 合并子问题
    // 因为我们已经知道 leftA 和 leftB 两个数组已经是从小到大排好序的数组，因此可以很简单地找出逆序对
    for(int i = 0, leftA_index = 0, rightA_index = 0; i < n; ++i) {
        
        // 左数组跑空
        // 该情况下已经不可能构成逆序对，无须处理逆序对个数
        if (leftA_index >= leftA_length) {
            
            a[i] = rightA[rightA_index];
            ++rightA_index;
            continue;
        }
        
        // 右数组跑空
        // 该情况下已经不可能构成逆序对，无须处理逆序对个数
        if (rightA_index >= rightA_length) {
            
            a[i] = leftA[leftA_index];
            ++leftA_index;
            continue;
        }
        
        // 左数组当前元素大于右数组当前元素
        // 只有这种情况需要处理逆序对个数，即左数组剩余元素（包括当前）都可以与右数组当前元素构成逆序对
        // 故逆序对个数需要增加左数组剩余元素个数
        if (leftA[leftA_index] > rightA[rightA_index]) {
            
            (*ipn) += (leftA_length - leftA_index);
            
            a[i] = rightA[rightA_index];
            ++rightA_index;
        }
        
        // 左数组当前元素小于等于于右数组当前元素
        // 不符合逆序对定义，因此无须处理逆序对个数
        else {
            
            a[i] = leftA[leftA_index];
            ++leftA_index;
        }
    }
    
    // 释放空间并返回
    delete [] leftA;
    delete [] rightA;
    return a;
}

int main(int argc, const char * argv[]) {
    
    // 共m个问题
    int m;
    cin >> m;
    
    // 新建逆序对个数数量对象
    int* ipn = new int(0);
    
    while((--m) >= 0) {
        
        // 初始化逆序对个数
        *ipn = 0;
        
        // 输入数组长度
        int n;
        cin >> n;
        
        // 输入数组
        int* a = new int[n];
        for (int i = 0; i < n; ++i) {
            cin >> a[i];
        }
        
        // 开始归并排序
        a = computeInversePairNum(a, n, ipn);
        
        // 输出逆序对个数
        cout << *ipn << endl;
        
        // 释放空间
        delete [] a;
    }
    
    // 释放空间
    delete ipn;
}