algorithm - 如果有序，使数组的每个元素连续的最小操作数

Question

给定一个数组，返回使数组的所有元素连续所需的最少操作次数。在一个操作中，数组的任何元素都可以被任何整数替换。例如 =>

arr = [6, 4, 1, 7, 10]

输出应该是continuousElementsArray(arr) = 2。通过转换1 -> 5 和10 -> 8 最终数组是

arr = [6, 4, 5, 7, 8]

连续意味着数字应该是连续的，如 {1,2,3} 或 {2,3,1}。这里顺序无关紧要。并且每个数字都应该是唯一的(不允许重复)。

Answer 1

我用下面的算法做了一些实验，得到了一些不错的结果。

将数字按升序排序

取最后一次连续数字(例如 [98, 99, 100] )或第一次连续数字(例如 [1, 2] )，以数字最少者为准。在这种情况下 [1, 2]会被选中，因为它只有 2 个元素。如果第一次和最后一次运行的长度相同，请选择其中一个

从开始/结束取数字，尽可能多地挤进最靠近中间的空隙。最接近中间意味着它们不太可能被重新编号两次或更多次

从 2 开始重复，直到不再有间隙

优化重新编号——见下文。

这是一个 Python implementation使用这个算法。不能保证它的解决方案是最佳的，但对于我仔细研究过的小案例，重新编号计数低得令人放心。它在几秒钟内解决了 5000 个数字和 1000 多个间隙(源中的测试数据)，并且最少的移动次数主观上是正确的。

$ python continuous.py
Original numbers: [1, 2, 5, 6, 9, 10, 13, 14, 19]
19 -> 3
14 -> 4
13 -> 7
10 -> 8
(4 renumbers)
Original order with renumbers:
[1, 2, 5, 6, 9, 8, 7, 4, 3]
Gaps in final output (check=0): 0
Sorted:
[1, 2, 3, 4, 5, 6, 7, 8, 9]
no of integers in original: 9

“运行”是一系列连续的整数，如 [45, 46, 47] . “间隙”是整数数组中一个或多个缺失的数字。 [1, 2, 5]包含一个缺口 [3, 4] .
我们的目标是将一系列数字中的差距减少到零。
通过在数字的末尾和开头从运行中删除数字，当运行消失时，间隙也消失了。重新编号这些外部数字以填补中间的空白也会减少空白。
在中间对数字重新编号要么对间隙的数量几乎没有影响，要么会产生多余的移动，要么会产生越来越大的间隙。
手工制作示例
取数字 [1, ..., 3, ..., 5, 6, ..., 9, 10, 11, ..., 13, ..., 19] : [7, 8]差距最接近中间(5的第三个差距)；运行 [1] (1 个数字) 与 run [19] 的大小相同(1 个号码) 所以 1从第一次运行中任意选择并重新编号为 7 . [7, 8]差距现在减少到 [8] ;因为 1已重新编号，不再有 [2]间隙或者，因为序列现在从数字 3 开始:

[1, 3, 5, 6, 9, 10, 11, 13, 19] -> [*x,* 3, 5, 6, *7,* 9, 10, 11, 13, 19]

( x 是重新编号之前的原始编号。) [8]差距最接近中间(3的第二个差距)； 3从头开始剥离并重新编号为 8 ，删除 [8]差距和 [4]差距:

[3, 5, 6, 7, 9, 10, 11, 13, 19] -> [*x,* 5, 6, 7, *8,* 9, 10, 11, 13, 19]

[12]差距最接近中间 - 或与 [14..19] 一样接近中间差距; [19]短于 [5..7]所以最后一次运行， [19]用作来源。号码 19重新编号为 12 ，堵塞 12间隙并移除 [14..18]差距:

[5, 6, 7, 8, 9, 10, 11, 13, 19] -> [5, 6, 7, 8, 9, 10, 11, *12,* 13, *x*]

因为没有更多的间隙，我们有一个不间断的数字序列 [5..13] .
但是如果 [14, 15, 16, 17, 18]间隙被选为中间间隙而不是 [12]差距？在这种情况下，我们会得到两个重新编号: 19 -> 14其次是 14 -> 12 .这些可以折叠成 19 -> 12 ，产生相同的结果。见下文。
答案是您移动了多少个数字:

1 -> 7, 3 -> 8, 19 -> 12 (3 moves)

优化重新编号
您可以通过折叠多余的重新编号(如果有)来进一步优化答案。没有一个数字需要多次更改。如果您有两个链接的重新编号，则可以将它们替换为一个重新编号。
例如，序列 [1, 3, 5, 7, 9]可以使用以下重新编号合并:

9 -> 6, 7 -> 2, 6 -> 4

这可以简化为:

9 -> 4, 7 -> 2

给予连续运行 [1, 2, 3, 4, 5]在 2 步而不是 3 步。