我将如何编写如下所示的算法？

Question

我有三个数组，由六个红色数字组成，范围从 1 到 6。可以有多个相同的数字。

例如 [1, 4, 3, 3, 6, 2], [5, 5, 2, 1, 3, 4] 和 [2, 4, 3, 1, 1, 6]

该算法的目标是按照以下规则将这些数组中的数字变为蓝色：

• 每个蓝色数字都必须是唯一的（1、2、3、4、5、6）
• 每个数组应该有 2 个蓝色数字
• 如果无法这样做，算法应该警告我

在这个例子中，蓝色数字可以是数组一中的 (1, 4)，数组二中的 (2, 5) 和数组三中的 (3, 6)。

编写一个可以做到这一点的算法是否现实？我正在寻找可以编写代码以使其工作的逻辑。

Answer 1

您可以将此问题简化为二分匹配。

如果我们考虑两组顶点，一组用于数组，一组用于数字，如果 n 是 A 的元素，则在数组 A 和数字 n 之间创建一条边，那么我们有一个二分图我们可以使用 any matching algorithm。然后，数组和数字之间的每个匹配表示该数字在该数组中是蓝色的。

这仅适用于为每个数组制作一个蓝色数字，但可以通过将每个数组作为顶点添加两次来扩展，从而每个数组获得两个匹配项，因此每个数组有两个蓝色数字。