4

可以说我有一组块。12个红色，8个蓝色，5个黄色，1个绿色。我需要创建一个算法，将这些对象输出到单个数组中，其中没有相邻的红色块，没有相邻的蓝色块等。输出应该如下所示：

红、蓝、红、蓝、红、蓝、黄、蓝、绿、红、黄等

到目前为止，在我的编程经验中，我不得不多次编写算法来执行此操作。我最后一次这样做是在大约 2 年前为一家初创公司工作。我在python中实现了这样一个算法，但是源代码不可用。我记得我至少花了 100 行来创作。

这个算法有名字吗？我不想再次实施它。

4

3 回答 3

6

我不知道这个问题的名称。下面是我想出的解决它的算法。

您需要跟踪剩余的每个块的#。

repeat:
output 1 block of largest color set.
output 1 block from the second largest color set.

输出：

rbrbrbrbrgrbrgrbrgrbr grbgy

注意：在运行此算法之前，您需要检查最大颜色集的大小是否大于 1 + 其他颜色大小的总和。如果是，则没有解决方案。

注意：不需要从第二大集合中挑选。循环中的第二个选择可以来自任何非最大的颜色集。

于 2012-06-14T20:41:28.167 回答
1

就在我的脑海中 - 创建一个队列，其中包含您想要以递减数量插入的所有块（即使用上面的示例队列将包含 12 个红色然后 8 个蓝色然后 5 个黄色然后 1 个绿色）。将队列中的一个元素插入数组的每个偶数索引，然后插入每个奇数索引（即在索引 0、2、4、6、8、10、12、14、16、18、20、22 处插入一个红色块，然后在 24、1、3、5、7、9、11、13 处插入蓝色，然后在 15、17、19、21 处插入黄色，在 23 处插入绿色）

请注意，对于某些块组合，此任务是不可能的 - 在运行算法之前，您必须检查具有最高编号的块集的块数是否不超过所有块的总和除以 2

于 2012-06-14T20:06:51.887 回答
0

  1. 首先你需要检查这样的数组是否存在。

    例如，如果您有 4 个红色而只有 1 个蓝色，则它不存在

    因此，如果最大集合的数量小于所有其他集合的总和减 1，则没有有效的解决方案

  2. 然后，您只需将您最大收藏的所有项目（例如红色）作为列表放在那里。

    在列表的每个项目之间，它是您可以插入其他元素的地方

    e.g. _ red _ red _ red _ red _ red _ red ...

  3. 现在，您可以将其他项目集合插入到这些位置。集合的顺序无关紧要。

    e.g. blue red blue red blue red blue red yellow red yellow red _ red _ red ..

    您需要始终从左到右（或始终从右到左）消耗这些点。

    每当您用完点时，您就会从左侧（或右侧）重新开始将项目插入新点。

    e.g. green blue _ red _ blue _ red _ blue _ red _ blue _ red _ yellow _ red ...
于 2012-06-14T21:12:55.303 回答