### 题目描述补充 **题目：全局和局部逆序数** 给定一个数组 `arr`，其中 `arr[i]` 是一个包含整数的数组（子数组），且所有子数组的长度相同。对于数组 `arr`，我们需要计算两种逆序数： 1. **全局逆序数**：考虑 `arr` 中所有元素（即所有子数组中的所有整数）形成的单一序列时，该序列中的逆序数对数量。逆序数对 `(i, j)` 指的是满足 `i < j` 且 `arr[k1][i] > arr[k2][j]` 的元素对，其中 `k1` 和 `k2` 是任意子数组的索引，且 `arr[k1][i]` 和 `arr[k2][j]` 分别是两个元素。 2. **局部逆序数**：对于 `arr` 中的每个子数组 `arr[i]`，分别计算该子数组内部的逆序数对数量。逆序数对 `(p, q)` 指的是满足 `p < q` 且 `arr[i][p] > arr[i][q]` 的元素对。 要求： - 编写函数来计算并返回全局逆序数和局部逆序数的数组，其中全局逆序数为第一个元素，局部逆序数数组为第二个元素（数组形式）。 - 时间复杂度需尽量优化，全局逆序数的计算可以考虑使用归并排序的思想。 ### 示例 **输入**: ``` arr = [[1, 3, 2], [2, 1, 4], [3, 2, 1]] ``` **输出**: ``` [4, [1, 1, 0]] ``` **解释**: - 全局逆序数有 4 对：(1, 2), (1, 4), (3, 2), (3, 4)。 - 第一个子数组 `[1, 3, 2]` 的局部逆序数为 1 对 (3, 2)。 - 第二个子数组 `[2, 1, 4]` 的局部逆序数为 1 对 (2, 1)。 - 第三个子数组 `[3, 2, 1]` 的局部逆序数为 0 对。 ### 示例代码 以下是使用 Python 编写的示例代码： ```python def merge_sort_and_count(arr): def merge(left, right): res, i, j = 0, 0, 0 inv_count = 0 while i < len(left) and j < len(right): if left[i] <= right[j]: result.append(left[i]) i += 1 else: result.append(right[j]) inv_count += len(left) - i # All remaining in left are greater j += 1 result.extend(left[i:]) result.extend(right[j:]) return inv_count def merge_sort_rec(arr): if len(arr) > 1: mid = len(arr) // 2 left_half = arr[:mid] right_half = arr[mid:] inv_left = merge_sort_rec(left_half) inv_right = merge_sort_rec(right_half) inv_merge = merge(left_half, right_half) return inv_left + inv_right + inv_merge return 0 global result result = [] total_inv = merge_sort_rec(arr) return total_inv, [merge_sort_and_count(sub) for sub in arr] # Test the function arr = [[1, 3, 2], [2, 1, 4], [3, 2, 1]] total_inv, local_invs = merge_sort_and_count([val for sub in arr for val in sub]) print([total_inv, [local_inv for _, local_inv in sorted(zip(arr, local_invs), key=lambda x: x[0])]]) ``` **注意**：由于直接计算全局逆序数需要先将所有子数组展平，上面的 Python 示例代码中并没有直接展示如何分离出每个子数组的局部逆序数。实际使用时，需要稍作修改以记录每个子数组的局部逆序数。这里为简化展示，只给出了全局逆序数的计算方式。局部逆序数的计算可以在递归函数中为每个子数组分别调用一个类似于 `merge_sort_and_count` 的函数来完成。 对于 PHP 和 JavaScript 的实现，逻辑与 Python 类似，主要区别在于语法细节和内置函数的使用上。在码小课网站中，你可以找到更多关于算法和数据结构的相关内容，帮助深入理解并实现这些概念。