如果有序，使数组的每个元素连续的最小操作数 [英] Minimum number of operations to make every element of an array consecutive if ordered

问题描述

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

Given an array, return the minimum number of operations required to make all the elements of the array continuous. In one operation, any element of the array can be replaced with any integer. For example =>

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

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

the output should be continuousElementsArray(arr) = 2. By converting 1 -> 5 and 10 -> 8 Final array is

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

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

Continuous mean that number should be consecutive like {1,2,3} or {2,3,1}. Here order doesn't matter. And every number should be unique (No repetition is allowed).

推荐答案

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

I've done some experiments with the following algorithm and got some good results.

1. 将数字按升序排序
2. 取最后一次连续数字(例如[98, 99, 100])或第一次连续数字(例如[1, 2])，以最少的数字为准.在这种情况下 [1, 2] 将被选中，因为它只有 2 个元素.如果第一次和最后一次运行的长度相同，请选择其中一个
3. 从开头/结尾取出数字，然后将尽可能多的数字挤到最靠近中间的空隙中.最接近中间意味着它们不太可能被重新编号两次或更多次
4. 从 2 开始重复，直到没有间隙
5. 优化重新编号——见下文.

1. sort numbers into ascending order
2. take the last run of consecutive numbers (e.g. [98, 99, 100]) or the first run of consecutive numbers (e.g. [1, 2]), whichever has the fewest numbers. In this case [1, 2] would be picked because it has only 2 elements. If the first and last runs are of the same length, choose one of them
3. take numbers from the start/end and squeeze as many as possible into the gap that's nearest the middle. Nearest the middle means they're less likely to be renumbered twice or more
4. repeat from 2 until there are no more gaps
5. optimise renumbers-- see below.

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

Here's a Python implementation that uses this algorithm. There's no guarantee that its solutions are optimal but the renumber counts are reassuringly low for small cases I've looked at closely. It solves for 5000 numbers and over 1000 gaps in a few seconds (test data in source) and the minimal number of moves is subjectively about right.

$ 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].

A "run" is a consecutive series of integers like [45, 46, 47]. A "gap" is one or more missing numbers in an integer array. [1, 2, 5] contains a gap [3, 4].

我们的目标是将一系列数字中的差距减少到零.

What we're aiming for is to reduce gaps in a series of numbers to zero.

通过从数字末尾和开头的运行中删除数字，当运行消失时，间隙也消失了.重新编号这些外部数字以填补中间的空白也会减少空白.

By taking numbers off the runs at the end and the beginning of the numbers, when a run disappears, a gap disappears too. Renumbering these outer numbers so they fill gaps in the middle also reduces gaps.

在中间对数字重新编号要么对间隙的数量几乎没有影响，要么会产生多余的移动，要么会产生更多更大的间隙.

Renumbering numbers in the middle either makes little difference to the number of gaps, creates redundant moves or creates more and bigger gaps.

取数字 [1, ..., 3, ..., 5, 6, ..., 9, 10, 11, ..., 13, ..., 19]:

[7, 8] 间隙离中间最近(5 的第三个间隙)；run [1] (1 number) 与 run [19] (1 number) 的大小相同，所以 1 是从第一次运行并重新编号为 7.[7, 8] 差距现在减少到 [8];由于 1 已重新编号，因此也不再存在 [2] 间隙，因为序列现在从数字 3 开始:

The [7, 8] gap is nearest the middle (3rd gap of 5); The run [1] (1 number) is the same size as run [19] (1 number) so 1 is arbitrarily chosen from the first run and renumbers as 7. The [7, 8] gap is now reduced to [8]; because 1 has been renumbered, there is no longer a [2] gap either, as the sequence now starts from the number 3:

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

(x 是重新编号之前的原始号码.)

(x is where the original number was before renumbering.)

[8] 间隙最接近中间(3 的第二个间隙)；3 从头开始​​剥离并重新编号为 8，去除 [8] 间隙和 [4]差距:

The [8] gap is nearest the middle (2nd gap of 3); 3 peels off from the start and renumbers as 8, removing the [8] gap and the [4] gap:

[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] 间隙:

The [12] gap is nearest the middle-- or as near the middle as the [14..19] gap; [19] is shorter than [5..7] so the last run, [19] is used as a source. The number 19 renumbers as 12, plugging the 12 gap and removing the [14..18] gap:

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

因为没有更多的间隙，我们有一个完整的数字序列[5..13].

Because there are no more gaps, we have an unbroken sequence of numbers [5..13].

但是如果 [14, 15, 16, 17, 18] 间隙被选为中间间隙而不是 [12] 间隙呢?在这种情况下，我们会得到两个重新编号:19 ->14 后跟 14 ->12.这些可以折叠成 19 ->;12，产生相同的结果.见下文.

But what if the [14, 15, 16, 17, 18] gap had been chosen as the middle gap instead of the [12] gap? In that case we'd get two renumbers: 19 -> 14 followed by 14 -> 12. These can be collapsed into 19 -> 12, yielding the same result. See below.

答案是您移动了多少个数字:

The answer is how many numbers you have moved:

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

优化重新编号

您可以通过折叠多余的重新编号(如果有)来进一步优化答案.没有一个数字需要多次更改.如果您有两个链接的重编号，则可以将它们替换为一个重编号.

Optimising Renumbers

You can optimise the answer further by collapsing redundant renumbers if there are any. No number needs changing more than once. If you have two renumbers that are chained they can be replaced by one renumber.

例如，序列 [1, 3, 5, 7, 9] 可以使用以下重新编号合并:

As an example, the sequence [1, 3, 5, 7, 9] could be consolidated using the following renumbers:

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

这可以简化为:

9 -> 4, 7 -> 2

连续运行 [1, 2, 3, 4, 5] 2 步而不是 3 步.

giving the continuous run [1, 2, 3, 4, 5] in 2 moves rather than 3.

这篇关于如果有序，使数组的每个元素连续的最小操作数的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！