给定一个源和阵列天线的最终，发现跳数在不到二次时间复杂度生成从源最终

Question

假设有一个整数数组（例如为[1 5 3 4 6]）。元素根据以下规则重新排列。每个元素都可以向前跳跃（向左），并在跳过的索引中滑动元素。该过程以第二索引中的元素开始（即5）。它有跳过元素1的选择，或者它可以保持在它自己的位置。如果它选择跳跃，则元素1向下滑动到索引2.让我们假设它选择跳跃，然后我们的结果数组将会是[5 1 3 4 6]。元素3现在可以跳过1或2个位置并重复该过程。如果在一个位置上跳跃3次，阵列现在是[5 3 1 4 6]，并且如果跳过两个位置，现在将是[3 5 1 4 6]。

这是很容易证明的元素的所有可能的排列是可以以这种方式。任何最终配置都可以通过一组独特的事件来达成。

的问题是，给定一个最终阵列和源阵列，发现在来自光源的阵列天线的最终到达所需要的跳的总数。 O（N^2）实现很容易找到，但我相信这可以在O（N）或O（NlogN）中完成。另外，如果不可能比O（N2）做得更好，那么知道这一点将是非常好的。

例如，如果最后一个数组为[3,5,1,4,6]和源阵列[1,5,3,4,6]，答案将是3.

我ö （N2）算法是这样的：你从源头数组的所有位置循环遍历，因为我们知道这是最后一个要移动的元素。这里是6，我们检查它在最终数组中的位置。我们计算所需跳数，并需要重新排列最终数组，以将该元素放置在源数组中的原始位置。重新排列步骤遍历数组中的所有元素，并且该过程遍历所有元素，因此O（N^2）。使用散列图或地图可以帮助搜索，但是在每个产生O（N^2）的步骤之后需要更新地图。

P.S.我试图用贝叶斯方式来模拟两个排列之间的相关性，这是一个小问题。任何关于修改生成过程以使问题更简单的想法也是有帮助的。

编辑：我发现我的答案。这正是Kendall Tau距离所做的。有一种简单的基于合并排序的算法可以在O（NlogN）中找到它。

Answer 1

将目标数组视为一个排序。目标阵列[2 5 4 1 3]可以被视为[1 2 3 4 5]，只是通过重新标记。您只需知道映射即可在常量时间内比较元素。在这种情况下，要比较4和5，请检查：index[4]=2 > index[5]=1（在目标阵列中）等4 > 5（含义：4必须在最后的5的右侧）。

所以你真的只是一个香草排序问题。排序与通常的数字排序不同。唯一改变的是你的比较功能。其余的基本上是一样的。分类可以在O(nlgn)或甚至O(n)（基数排序）中实现。也就是说，您还有一些额外的限制：您必须在原地进行排序，并且只能交换两个相邻的元素。

强大而简单的候选人将是selection sort，这将做到这一点在O(n^2)时间。在每次迭代中，您都会识别“未放置”部分中的“最左边”剩余元素，并交换它，直到它落在“放置”部分的末尾。通过使用适当的数据结构（在O(lgn)时间内识别“最左边的”剩余元素的优先级队列），它可以改进为O(nlgn)。由于nlgn是基于比较的排序的下限，我真的认为你可以做得比这更好。

编辑：所以你根本不感兴趣的交换顺序，只有交换所需的最小数量。这正好是数组中的inversions（适应您的特定需求：“非自然排序”比较函数，但不会改变数学）。请参阅this answer以获取该断言的证据。

查找倒数的一种方法是调整合并排序算法。因为你必须实际对数组进行排序来计算它，结果仍然是O(nlgn)时间。有关实现，请参见this answer或this（同样，请记住，您必须修改）。

Answer 2

从你的答案我假设跳数是将原始数组转换为最终数组所需的相邻元素的交换总数。

我建议使用类似插入排序，但没有插入部分 - 数组中的数据不会被改变。

你可以使队列t作为带计数器的平衡二叉搜索树（子树中的元素数）。

可以添加元素吨，从吨，平衡吨为O除去元素和找到元素位置在吨（日志C）时间，其中C是在吨元件的数目。

找到元素位置的几句话。它由二进制搜索和跳过的左侧（如果您保留分支上的元素，则为中间元素+1）累计。

关于平衡/添加/移除的几句话。您必须从已移除/添加的元素/子树和更新计数器向上遍历。对于插入+余额和删除+余额，操作总数仍然保持在O（log C）。

让我们吨是（平衡搜索树）队列，p是当前原始数组索引，q被最终数组索引，原数组是一个，最终阵列是˚F。

现在我们已经1个循环从左侧开始（说，p = 0，q = 0）：

• 如果一个 [p] == ˚F [q]，则原始数组元素跳过整个队列。添加t.count至答案，增量p，增量q。

• 如果一个 [p]！= ˚F [q]和˚F [q]不在吨，然后插入一个 [p]到t和增量p。

• 如果一个 [p]！= ˚F [q]和f [Q]是在吨，然后添加F [Q]的在队列回答位置，取出f [q] from t and increment q。

我喜欢的魔法，这将确保这一进程将p和q移动到阵列的端部在相同的时间，如果阵列是真的一个阵列的排列。不过，您应该检查p和q溢出来检测不正确的数据，因为我们没有真正快速的方法来证明数据是正确的。