2

假设您有一个整数数组（例如 [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]。

很容易证明所有可能的元素排列都是可能的。此外，任何最终配置都可以通过一组独特的事件来实现。

问题是，给定一个最终数组和一个源数组，找出从源到达最终数组所需的总跳数。AO(N^2) 的实现很容易找到，但是我相信这可以在 O(N) 或 O(NlogN) 中完成。此外，如果不可能做得比 O(N2) 更好，那么很高兴知道。

例如，如果最终数组是 [3,5,1,4,6]，源数组是 [1,5,3,4,6]，则答案将为 3。

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

PS我正在尝试以贝叶斯方式对两个排列之间的相关性进行建模，这是其中的一个子问题。任何关于修改生成过程以使问题更简单的想法也是有帮助的。

编辑：我找到了我的答案。这正是 Kendall Tau 距离所做的。有一个简单的基于合并排序的算法可以在 O(NlogN) 中找到这一点。

4

2 回答 2

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)（基数排序）。也就是说，您有一些额外的限制：您必须就地排序，并且您只能交换两个相邻的元素。

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

编辑：所以你对交换的顺序根本不感兴趣，只需要最少的交换次数。这正是数组中的反转次数（适应您的特定需求：“非自然排序”比较函数，但它不会改变数学）。有关该断言的证明，请参见此答案。

找到反转次数的一种方法是调整合并排序算法。由于您必须实际对数组进行排序才能计算它，所以结果仍然是O(nlgn)时间。有关实现，请参阅此答案或此（再次记住，您必须适应）。

于 2016-11-11T16:23:03.937 回答
1

根据您的回答，我假设跃点数是将原始数组转换为最终数组所需的相邻元素交换的总数。

我建议使用诸如插入排序之类的东西，但没有插入部分 - 数组中的数据不会被更改。

您可以将停滞的料斗的队列t设置为带有计数器的平衡二叉搜索树（子树中的元素数）。

您可以将元素添加到t ，从t中删除元素，平衡t并在 O(log C) 时间内找到t中的元素位置，其中 C 是t中的元素数。

关于寻找元素位置的几句话。它由二进制搜索和跳过的左侧（如果将元素保留在分支上，中间元素+1）计数的累积组成。

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

让我们t是（平衡搜索树）队列，p是当前原始数组索引，q是最终数组索引，原始数组是a，最终数组是f。

现在我们有 1 个从左侧开始的循环（例如，p =0，q =0）：

  • 如果a [ p ] == f [ q ]，则原始数组元素会跳过整个队列。将t.count添加到答案中，增加p，增加q。

  • 如果a [ p ] != f [ q ] 并且f [ q ] 不在 t 中，则将a [ p ] 插入t并增加p。

  • 如果a [ p ] != f [ q ] 并且 f[q] 在t中，则将 f[q] 在队列中的位置添加到应答中，从t中删除f [ q ]并增加q。

如果数组真的是一个数组的排列，我喜欢这样的魔法，它可以确保这个过程将 p 和 q 同时移动到数组的末端。尽管如此，您可能应该检查 p 和 q 溢出以检测不正确的数据，因为我们没有真正更快的方法来证明数据是正确的。

于 2016-11-11T17:06:45.750 回答