LCR 170 交易逆序对的总数（Java & JS & Python & C & C++）

题目来源

LCR 170. 交易逆序对的总数 - 力扣（LeetCode）

题目描述

在股票交易中，如果前一天的股价高于后一天的股价，则可以认为存在一个「交易逆序对」。请设计一个程序，输入一段时间内的股票交易记录 record，返回其中存在的「交易逆序对」总数。

示例

输入：record = [9, 7, 5, 4, 6]
输出：8
解释：交易中的逆序对为 (9, 7), (9, 5), (9, 4), (9, 6), (7, 5), (7, 4), (7, 6), (5, 4)。

提示

• 0 <= record.length <= 50000

题目解析

本题最优策略是使用归并排序来解题。

为什么会联想到归并排序呢？

如果你还不了解归并排序，可以看下这篇博客：

算法设计 - 归并排序（Java & JS & Python & C & C++）-CSDN博客https://fcqian.blog.csdn.net/article/details/141190862?spm=1001.2014.3001.5502

在归并排序过程中，我们会合并两个有序子数组，得到一个有序的大数组。

而在 “合并两个有序子数组” 的过程中，我们就可以计算出逆序对数量。比如下面例子：

之后就是循环上面逻辑了。

即，我们在合并两个有序子数组的过程中，如果发现 nums[j] < nums[i]，其中nums[j]为后半部分子数组元素，nums[i] 为前半部分子数组元素，则此时就可以产生逆序对。

且由于 nums前半部分 [L, mid] 是升序的，因此 [i, mid] 范围的元素都可以和 nums[j] 产生逆序对，即产生 mid - i + 1 个逆序对。

下面代码实现，其实只是在归并排序的 mergeTwoOrderedArray 过程中加了一个逆序对数量统计逻辑。

大家可以对比 算法设计 - 归并排序（Java & JS & Python & C & C++）-CSDN博客

和本题的代码。

Java算法源码

class Solution {
    public static int count; // 记录逆序对总数

    public int reversePairs(int[] record) {
        count = 0; // 初始化为0

        if(record.length >= 2) { // 如果record不足两个元素，则无法形成逆序对
            mergeSort(record, 0, record.length - 1);
        }

        return count;
    }

    // 归并排序
    public static void mergeSort(int[] nums, int l, int r) {
        if (l == r) return;

        int mid = (l + r) / 2;

        mergeSort(nums, l, mid);
        mergeSort(nums, mid + 1, r);

        mergeTwoOrderedArray(nums, l, r);
    }

    // 合并两个有序子数组
    public static void mergeTwoOrderedArray(int[] nums, int l, int r) {
        int n = r - l + 1;
        int mid = (l + r) / 2;

        int i = l;
        int j = mid + 1;

        int[] tmp = new int[n];
        for (int k = 0; k < n; k++) {
            if (i == mid + 1) {
                tmp[k] = nums[j++];
                // 此时 i 指向 mid + 1, 所以 mid - i + 1 计算结果为0
                // count += mid - (mid + 1) - 1
            } else if (j == r + 1) {
                tmp[k] = nums[i++];
            } else if (nums[i] <= nums[j]) {
                tmp[k] = nums[i++];
            } else {
                count += mid - i + 1; // 合并两个有序子数组过程中，收集逆序对数量
                tmp[k] = nums[j++];
            }
        }

        System.arraycopy(tmp, 0, nums, l, n);
    }
}

JavaScript算法源码

/**
 * @param {number[]} record
 * @return {number}
 */

let count; // 记录逆序对总数

var reversePairs = function (record) {
    count = 0;  // 初始化为0

    if (record.length >= 2) {  // 如果record不足两个元素，则无法形成逆序对
        mergeSort(record, 0, record.length - 1);
    }

    return count;
};

function mergeSort(nums, l, r) {
    if (l == r) return;

    const mid = (l + r) >> 1;

    mergeSort(nums, l, mid);
    mergeSort(nums, mid + 1, r);

    mergeTwoOrderedArray(nums, l, r);
}

function mergeTwoOrderedArray(nums, l, r) {
    const n = r - l + 1;
    const mid = (l + r) >> 1;

    let i = l;
    let j = mid + 1;

    const tmp = new Array(n);

    for (let k = 0; k < n; k++) {
        if (i == mid + 1) {
            // 此时 i 指向 mid + 1, 所以 mid - i + 1 计算结果为0
            // count += mid - (mid + 1) - 1
            tmp[k] = nums[j++];
        } else if (j == r + 1) {
            tmp[k] = nums[i++];
        } else if (nums[i] <= nums[j]) {
            tmp[k] = nums[i++];
        } else {
            count += mid - i + 1; // 合并两个有序子数组过程中，收集逆序对数量
            tmp[k] = nums[j++];
        }
    }

    for (let k = 0; k < n; k++) {
        nums[l + k] = tmp[k];
    }
}

Python算法源码

count = 0  # 记录逆序对总数

# 合并两个有序子数组
def mergeTwoOrderedArray(nums, l, r):
    global count

    n = r - l + 1
    mid = (l + r) // 2

    i = l
    j = mid + 1

    tmp = [0] * n

    for k in range(n):
        if i == mid + 1:
            # 此时 i 指向 mid + 1, 所以 mid - i + 1 计算结果为0
            # count += mid - (mid + 1) - 1
            tmp[k] = nums[j]
            j += 1
        elif j == r + 1:
            tmp[k] = nums[i]
            i += 1
        elif nums[i] <= nums[j]:
            tmp[k] = nums[i]
            i += 1
        else:
            count += mid - i + 1  # 合并两个有序子数组过程中，收集逆序对数量
            tmp[k] = nums[j]
            j += 1

    for k in range(n):
        nums[l + k] = tmp[k]


# 归并排序
def mergeSort(nums, l, r):
    if l == r:
        return

    mid = (l + r) // 2

    mergeSort(nums, l, mid)
    mergeSort(nums, mid + 1, r)

    mergeTwoOrderedArray(nums, l, r)

class Solution(object):
    def reversePairs(self, record):
        """
        :type record: List[int]
        :rtype: int
        """
        global count
        count = 0  # 初始化为0

        if len(record) >= 2:  # 如果record不足两个元素，则无法形成逆序对
            mergeSort(record, 0, len(record) - 1)
        
        return count

C算法源码

int count; // 记录逆序对总数

void mergeTwoOrderedArray(int* nums, int l, int r) {
    int n = r - l + 1;
    int mid = (l + r) / 2;

    int i = l;
    int j = mid + 1;

    int tmp[n];

    for (int k = 0; k < n; k++) {
        if (i == mid + 1) {
            // 此时 i 指向 mid + 1, 所以 mid - i + 1 计算结果为0
            // count += mid - (mid + 1) - 1
            tmp[k] = nums[j++];
        } else if (j == r + 1) {
            tmp[k] = nums[i++];
        } else if (nums[i] <= nums[j]) {
            tmp[k] = nums[i++];
        } else {
            count += mid - i + 1; // 合并两个有序子数组过程中，收集逆序对数
            tmp[k] = nums[j++];
        }
    }

    for (int k = 0; k < n; k++) {
        nums[l + k] = tmp[k];
    }
}

void mergeSort(int* nums, int l, int r) {
    if (l == r)
        return;

    int mid = (l + r) / 2;

    mergeSort(nums, l, mid);
    mergeSort(nums, mid + 1, r);

    mergeTwoOrderedArray(nums, l, r);
}

int reversePairs(int* record, int recordSize) {
    count = 0; // 初始化为0

    if (recordSize >= 2) { // 如果record不足两个元素，则无法形成逆序对
        mergeSort(record, 0, recordSize - 1);
    }

    return count;
}

C++算法源码

class Solution {
public:
    int count; // 记录逆序对总数

    int reversePairs(vector<int>& record) {
        count = 0; // 初始化为0

        if (record.size() >= 2) { // 如果record不足两个元素，则无法形成逆序对
            mergeSort(record, 0, record.size() - 1);
        }

        return count;
    }

    // 合并两个有序子数组
    void mergeTwoOrderedArray(vector<int>& nums, int l, int r) {
        int n = r - l + 1;
        int mid = (l + r) / 2;

        int i = l;
        int j = mid + 1;

        int tmp[n];

        for (int k = 0; k < n; k++) {
            if (i == mid + 1) {
                // 此时 i 指向 mid + 1, 所以 mid - i + 1 计算结果为0
                // count += mid - (mid + 1) - 1
                tmp[k] = nums[j++];
            } else if (j == r + 1) {
                tmp[k] = nums[i++];
            } else if (nums[i] <= nums[j]) {
                tmp[k] = nums[i++];
            } else {
                count +=
                    mid - i + 1; // 合并两个有序子数组过程中，收集逆序对数量
                tmp[k] = nums[j++];
            }
        }

        for (int k = 0; k < n; k++) {
            nums[l + k] = tmp[k];
        }
    }

    // 归并排序
    void mergeSort(vector<int>& nums, int l, int r) {
        if (l == r)
            return;

        int mid = (l + r) / 2;

        mergeSort(nums, l, mid);
        mergeSort(nums, mid + 1, r);

        mergeTwoOrderedArray(nums, l, r);
    }
};