归并分治

归并排序

912. 排序数组

#include <iostream>
#include <vector>

using namespace std;

class Solution {
public:
    // 分治-治
    void merge(vector<int> &arr, int left, int mid, int right, vector<int> &temp) {
        // [left, mid]和[mid+1, right]两个有序数组
        int i = left;
        int j = mid + 1;
        int index = 0;
        while (i <= mid && j <= right) {
            if (arr[i] < arr[j])
                temp[index++] = arr[i++];
            else
                temp[index++] = arr[j++];
        }
        // 剩余元素直接放入temp
        while (i <= mid) temp[index++] = arr[i++];
        while (j <= right) temp[index++] = arr[j++];
        // 放回原数组
        index = 0;
        while (left <= right) arr[left++] = temp[index++];
    }

    // 分治-分
    // T(n) = 2 * T(n/2) + O(n)
    // a = 2, b = 2, c = 1, 根据 master 公式，时间复杂度为 O(n * logn)
    // 空间复杂度 O(n)
    void divide(vector<int> &arr, int left, int right, vector<int> &temp) {
        if (left >= right) return;
        int mid = left + ((right - left) >> 2);
        // 左边归并排序
        divide(arr, left, mid, temp);
        // 右边归并排序
        divide(arr, mid + 1, right, temp);
        // 合并两个有序序列
        merge(arr, left, mid, right, temp);
    }

    // 递归版归并排序
    void mergeSort(vector<int> &arr) {
        vector<int> temp(arr.size());
        divide(arr, 0, arr.size() - 1, temp);
    }

    vector<int> sortArray(vector<int> &nums) {
        mergeSort(nums);
        return nums;
    }
};

#include <iostream>
#include <vector>

using namespace std;

class Solution {
public:
    // 分治-治
    void merge(vector<int> &arr, int left, int mid, int right, vector<int> &temp) {
        // [left, mid]和[mid+1, right]两个有序数组
        int i = left;
        int j = mid + 1;
        int index = 0;
        while (i <= mid && j <= right) {
            if (arr[i] < arr[j])
                temp[index++] = arr[i++];
            else
                temp[index++] = arr[j++];
        }
        // 剩余元素直接放入temp
        while (i <= mid) temp[index++] = arr[i++];
        while (j <= right) temp[index++] = arr[j++];
        // 放回原数组
        index = 0;
        while (left <= right) arr[left++] = temp[index++];
    }


    // 非递归版归并排序
    void mergeSort(vector<int> &arr) {
        vector<int> temp(arr.size());
        int n = arr.size();
        // 执行 O(logn) 次
        for (int left, mid, right, step = 1; step < n; step <<= 1) {
            left = 0;
            // O(n)
            while (left < n) {
                mid = left + step - 1;
                // 没有右侧
                if (mid + 1 >= n) break;
                // 求右边界
                right = min(left + (step << 1) - 1, n - 1);
                merge(arr, left, mid, right, temp);
                // 找下一组
                left = right + 1;
            }
        }
    }

    vector<int> sortArray(vector<int> &nums) {
        mergeSort(nums);
        return nums;
    }
};

归并分治

• 思考一个问题在大范围上的答案，是否等于：左部分答案 + 右部分答案 + 跨越左右产生的答案
• 计算跨越左右产生的答案时，如果加上左右两侧都有序，能不能简化计算

计算数组的小和

#include <iostream>
#include <vector>

using namespace std;

vector<int> temp;

void merge(vector<int> &arr, int left, int mid, int right) {
    int i = left;
    int j = mid + 1;
    int index = 0;
    while (i <= mid && j <= right) {
        if (arr[i] <= arr[j]) {
            temp[index++] = arr[i++];
        } else {
            temp[index++] = arr[j++];
        }
    }
    while (i <= mid) temp[index++] = arr[i++];
    while (j <= right) temp[index++] = arr[j++];
    index = 0;
    while (left <= right) arr[left++] = temp[index++];
}

// 返回小和，且把数组这一段变成有序
long divide(vector<int> &arr, int left, int right) {
    if (left >= right) return 0;
    int mid = left + ((right - left) >> 1);
    // 分别计算两侧的小和
    long leftSum = divide(arr, left, mid);
    long rightSum = divide(arr, mid + 1, right);
    // 两部分都已经有序
    long midSum = 0;
    for (int l = left, r = mid + 1, sum = 0; r <= right; r++) {
        // 找到第一个大于 arr[r] 的位置
        while (l <= mid && arr[l] <= arr[r]) {
            sum += arr[l++];
        }
        midSum += sum;
    }

    merge(arr, left, mid, right);
    return leftSum + midSum + rightSum;
}

int main() {
    int n;
    cin >> n;
    vector<int> arr(n);
    temp.resize(n);
    for (int i = 0; i < n; ++i)
        cin >> arr[i];
    cout << divide(arr, 0, n - 1);
}

493. 翻转对

#include <iostream>
#include <vector>

using namespace std;

class Solution {
public:
    vector<int> temp;

    void merge(vector<int> &arr, int left, int mid, int right) {
        int i = left;
        int j = mid + 1;
        int index = 0;
        while (i <= mid && j <= right) {
            if (arr[i] <= arr[j]) {
                temp[index++] = arr[i++];
            } else {
                temp[index++] = arr[j++];
            }
        }
        while (i <= mid) temp[index++] = arr[i++];
        while (j <= right) temp[index++] = arr[j++];
        index = 0;
        while (left <= right) arr[left++] = temp[index++];
    }

    int divide(vector<int> &nums, int left, int right) {
        if (left >= right) return 0;
        int mid = left + ((right - left) >> 1);
        int leftSum = divide(nums, left, mid);
        int rightSum = divide(nums, mid + 1, right);

        int midSum = 0;
        for (int l = left, r = mid + 1, sum = 0; l <= mid; ++l) {
            while (r <= right && ((long) nums[l] > (long) 2 * nums[r])) {
                sum++;
                r++;
            }
            midSum += sum;
        }

        merge(nums, left, mid, right);
        return leftSum + midSum + rightSum;
    }

    int reversePairs(vector<int> &nums) {
        temp.resize(nums.size());
        return divide(nums, 0, nums.size() - 1);
    }
};