给定源和最终数组，以小于二次时间复杂度的方式找到从源生成最终的跳数
Given a source and a final array, find the number of hops to generate final from the source in less than quadratic time complexity
假设您有一个整数数组（例如 [1 5 3 4 6]）。元素根据以下规则重新排列。每个元素都可以向前跳（向左）并滑动它跳过的那些索引中的元素。该过程从第二个索引中的元素（即 5）开始。它可以选择跳过元素 1 或者它可以留在它自己的 position.If 它确实选择跳跃，元素 1 向下滑动到索引 2。让我们假设它确实选择跳跃并且我们的结果数组将是[5 1 3 4 6]。元素 3 现在可以跳过 1 或 2 个位置并重复该过程。如果在一个位置上跳了 3 次，则数组现在将为 [5 3 1 4 6]，如果它在两个位置上跳了 3 次，则现在为 [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。
我的 O(N2) 算法是这样的：从末尾开始循环遍历源数组的所有位置，因为我们知道这是要移动的最后一个元素。这里是 6，我们检查它在最终数组中的位置。我们计算所需的跃点数，并需要重新排列最终数组以将该元素放在其在源数组中的原始位置。重新排列步骤遍历数组中的所有元素，并且该过程遍历所有元素，因此 O(N^2)。使用 Hashmap 或 map 可以帮助搜索，但是需要在 O(N^2) 的每个步骤之后更新 map。
P.S。我正在尝试以贝叶斯方式对两个排列之间的相关性进行建模，这是其中的一个子问题。任何关于修改生成过程以使问题更简单的想法也很有帮助。
编辑：我找到了答案。这正是 Kendall Tau 距离所做的。有一个简单的基于合并排序的算法可以在 O(NlogN) 中找到它。
将目标数组视为一个排序。目标数组 [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) 时间内完成。在每次迭代中，您识别 "unplaced" 部分中剩余的 "leftiest" 元素并交换它，直到它落在 "placed" 部分的末尾。它可以通过使用适当的数据结构（用于在 O(lgn) 时间内识别 "leftiest" 剩余元素的优先级队列）改进到 O(nlgn)。由于 nlgn 是基于比较的排序的下限，我真的不认为你能做得更好。
编辑: 所以你对交换的顺序根本不感兴趣，只关心所需的最小交换次数。这正是证明该断言的 inversions in the array (adapted to your particular needs: "non natural ordering" comparison function, but it doesn't change the maths). See this answer 的数量。
找到倒置次数的一种方法是采用归并排序算法。由于您必须实际对数组进行排序才能计算它，结果仍然是 O(nlgn) 时间。有关实现，请参阅 this answer or this（再次提醒，您必须适应）。
根据你的回答，我假设跃点数是将原始数组转换为最终数组所需的相邻元素交换总数。
我建议使用插入排序之类的东西，但没有插入部分——数组中的数据不会被改变。
您可以将停滞的漏斗的队列 t 作为带有计数器（子树中元素的数量）的平衡二叉搜索树。
您可以将元素添加到 t，从 t 中删除元素，平衡 t 和在 O(log C) 时间内找到 t 中的元素位置，其中 C 是 t.
中的元素数
关于查找元素位置的几句话。它由二进制搜索组成，累积跳过的左侧（如果将元素保留在分支上，则中间元素 +1）计数。
关于 balancing/addition/removal 的几句话。您必须从 removed/added element/subtree 向上遍历并更新计数器。 insert+balance 和 remove+balance 的操作总数仍然保持在 O(log C)。
让我们t是那个（平衡搜索树）队列，p是当前原始数组索引，q 是最终数组索引，原始数组是 a，最终数组是 f.
现在我们有 1 个循环从左侧开始（比如，p=0，q=0）：
如果a[p] == f[q]，则原数组元素跳遍整个队列。答案加t.count，递增p，递增q.
If a[p] != f[q]和f[q]不在t中，则插入a[p] 到 t 并递增 p.
If a[p] != f[q]且f[q]在t，则将f[q]在queue中的位置加入回答，去掉 f[q] 从 t 递增 q.
我喜欢这种魔法，如果数组真的是一个数组的排列，它可以确保此过程将同时将 p 和 q 移动到数组的末端。然而，您可能应该检查 p 和 q 溢出以检测不正确的数据，因为我们没有真正更快的方法来证明数据是正确的。
假设您有一个整数数组（例如 [1 5 3 4 6]）。元素根据以下规则重新排列。每个元素都可以向前跳（向左）并滑动它跳过的那些索引中的元素。该过程从第二个索引中的元素（即 5）开始。它可以选择跳过元素 1 或者它可以留在它自己的 position.If 它确实选择跳跃，元素 1 向下滑动到索引 2。让我们假设它确实选择跳跃并且我们的结果数组将是[5 1 3 4 6]。元素 3 现在可以跳过 1 或 2 个位置并重复该过程。如果在一个位置上跳了 3 次，则数组现在将为 [5 3 1 4 6]，如果它在两个位置上跳了 3 次，则现在为 [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。
我的 O(N2) 算法是这样的：从末尾开始循环遍历源数组的所有位置，因为我们知道这是要移动的最后一个元素。这里是 6，我们检查它在最终数组中的位置。我们计算所需的跃点数，并需要重新排列最终数组以将该元素放在其在源数组中的原始位置。重新排列步骤遍历数组中的所有元素，并且该过程遍历所有元素，因此 O(N^2)。使用 Hashmap 或 map 可以帮助搜索，但是需要在 O(N^2) 的每个步骤之后更新 map。
P.S。我正在尝试以贝叶斯方式对两个排列之间的相关性进行建模，这是其中的一个子问题。任何关于修改生成过程以使问题更简单的想法也很有帮助。
编辑：我找到了答案。这正是 Kendall Tau 距离所做的。有一个简单的基于合并排序的算法可以在 O(NlogN) 中找到它。
将目标数组视为一个排序。目标数组 [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) 时间内完成。在每次迭代中，您识别 "unplaced" 部分中剩余的 "leftiest" 元素并交换它，直到它落在 "placed" 部分的末尾。它可以通过使用适当的数据结构（用于在 O(lgn) 时间内识别 "leftiest" 剩余元素的优先级队列）改进到 O(nlgn)。由于 nlgn 是基于比较的排序的下限，我真的不认为你能做得更好。
编辑: 所以你对交换的顺序根本不感兴趣，只关心所需的最小交换次数。这正是证明该断言的 inversions in the array (adapted to your particular needs: "non natural ordering" comparison function, but it doesn't change the maths). See this answer 的数量。
找到倒置次数的一种方法是采用归并排序算法。由于您必须实际对数组进行排序才能计算它，结果仍然是 O(nlgn) 时间。有关实现，请参阅 this answer or this（再次提醒，您必须适应）。
根据你的回答，我假设跃点数是将原始数组转换为最终数组所需的相邻元素交换总数。
我建议使用插入排序之类的东西，但没有插入部分——数组中的数据不会被改变。
您可以将停滞的漏斗的队列 t 作为带有计数器（子树中元素的数量）的平衡二叉搜索树。
您可以将元素添加到 t，从 t 中删除元素，平衡 t 和在 O(log C) 时间内找到 t 中的元素位置，其中 C 是 t.
中的元素数关于查找元素位置的几句话。它由二进制搜索组成，累积跳过的左侧（如果将元素保留在分支上，则中间元素 +1）计数。
关于 balancing/addition/removal 的几句话。您必须从 removed/added element/subtree 向上遍历并更新计数器。 insert+balance 和 remove+balance 的操作总数仍然保持在 O(log C)。
让我们t是那个（平衡搜索树）队列，p是当前原始数组索引，q 是最终数组索引，原始数组是 a，最终数组是 f.
现在我们有 1 个循环从左侧开始（比如，p=0，q=0）：
如果a[p] == f[q]，则原数组元素跳遍整个队列。答案加t.count，递增p，递增q.
If a[p] != f[q]和f[q]不在t中，则插入a[p] 到 t 并递增 p.
If a[p] != f[q]且f[q]在t，则将f[q]在queue中的位置加入回答，去掉 f[q] 从 t 递增 q.
我喜欢这种魔法，如果数组真的是一个数组的排列，它可以确保此过程将同时将 p 和 q 移动到数组的末端。然而，您可能应该检查 p 和 q 溢出以检测不正确的数据，因为我们没有真正更快的方法来证明数据是正确的。