sorting - 计算涉及大于某个值的元素之间交换的反转

Question

这是一个家庭作业问题，我花了很多时间思考。

假设我有一个未排序的整数数组和一个给定的整数 d。任务是计算涉及交换大于 d 的反转次数。

例如，给定一个输入数组 (3, 4, 3, 1) 和 d = 2，则此类反转的数量为 1，因为仅计算 4 和 1 之间的反转。其他反演的差值小于 2。

当然，计算反转次数的一种简单方法是遍历列表的每个数字，并在该数字之前添加元素的数量，该数字更小，差异大于 d。然而，这是一个^2算法。而是需要一个 n \log n 算法。

这里给出了另一种更有效的算法，我们对输入数组执行归并排序并直接从那里计数。 https://www.geeksforgeeks.org/counting-inversions-subarrays-given-size/

但是，我无法修改它以获得正确的答案。

我的方法是这样的：

在合并排序的“合并”步骤中，如果左子数组的第一项较小，则只需将其添加到已排序的数组中并继续。

否则，我将左子数组中的项数比右子数组的第一项大 d 所需的反转次数增加。

尽管如此，我仍然无法获得正确的答案。

有人可以帮帮我吗？谢谢你。

标签： sorting

Answer 1

在合并过程中，如果左子数组 A[i] 的索引 i 的元素大于右子数组 A[j] 的索引 j 的元素，就会发生 ji 交换。

对差值大于 A[i...j-1] 的子数组中的值的最小元素进行二分搜索。那么大于该值的元素之间的交换次数将为 j 减去这个最小元素的索引。