给定一个由红色和蓝色球组成的字符串，找出将颜色分组所需的最小交换次数。

Question

我们有一个形如：RBBR 的字符串，其中 R 代表红色，B 代表蓝色。

我们需要找到将颜色归类在一起所需的最小交换次数。对于上述情况，答案是 1，可得到 RRBB 或 BBRR。

我觉得在这里使用算法来排序部分排序的数组会很有用，因为简单的排序可以给我们交换的次数，但我们想要的是 最小 交换次数。

有什么想法吗？

据说这是微软的面试题，参见 这里。

- efficiencyIsBliss

---

这里似乎需要动态规划和A*路径搜索算法。 - Phrogz

我对多颜色球排序所需的最小交换次数这个更一般的问题很感兴趣。我在回答中提供的算法在球的数量上是线性的，但在颜色数量上是阶乘级别的（因为可能的目标字符串数量是涉及颜色的排列）。有更好的方法吗？ - Null Set

@Null Set：@bronzerbeard提供了一个答案，引用了关于排序三种颜色字符串的荷兰国旗问题（http://en.wikipedia.org/wiki/Dutch_national_flag_problem），也许这可以作为一个起点。 - Matthieu M.

Answer 1

对字符串进行一次遍历，计算红色（#R）和蓝色（#B）的数量。然后进行第二次遍历，计算前 #R 个球中红色球的数量（#r）以及前 #B 个球中蓝色球的数量（#b）。(#R-#r) 和 (#B-#b) 中较小的值将是所需交换的最小次数。

- Null Set

---

我恐怕在这方面已经超出了我的能力范围。我无法确定你的观点是对还是错，你能解释一下你得出那些公式的方式吗？ - Matthieu M.

@Matthieu M.：据我所知，目标配置必须是以下两种之一：RR...RBB...B或BB...BRR...R。上面的代码只是计算通过交换哪一个更便宜实现这两个中的一个。 - Rafał Dowgird

@Matthieu 一旦您知道有多少个红色和蓝色，您就会知道这两种可能的结束字符串看起来是什么样子的，要么所有红色在右边，要么所有蓝色在右边。您只需要找出这两个字符串中哪一个更“接近”起始字符串即可。 - Null Set

@Matthieu：一旦你知道了红色和蓝色球的数量，你就知道了两个可能的结尾样式，要么全部红色在右边，要么全部蓝色在右边。你只需计算这两个字符串中哪一个更接近起始字符串即可。你可以通过计算空间中将充满红色或蓝色的“孔”的数量来实现这一点。每个目标颜色当前未占用的位置都需要从字符串另一侧进行交换。然后你只需选择需要更少交换的配置即可。 - Null Set

谢谢，我之前没太明白#R - #r是指#R个球中"空位"的数量。一旦理解了这点，剩下的就很简单了。非常好的解决方案。 - Matthieu M.

Answer 2

我们需要将给定的字符串S转换为最终字符串F = R^a B^b或B^b R^a。S和F之间的差异数量应该是偶数，因为对于每个错位的R都会有一个互补的错位的B。那么为什么不找到S和两个可能的F之间的最小差异数量，并将其除以2呢？

例如，给定S = RBRRBRBR，应该转换为RRRRRBBB或BBBRRRRR。

比较每个可能性的每个字符的S和F之间的差异，每个可能的最终字符串都有4个差异，因此无论如何最小交换次数都是2。

- aaa

Answer 3

这不是一个技术性的答案，但我更多地凭直觉看待了这个问题。

RRBBBBR 可以被缩减为 RBR，因为一组 R 可以作为一个单元块移动。这意味着数组实际上只是 N 个 RB 集合。

唯一重要的是 N 个 RB 块集的数量（包括最后一个不完整的块）。

• RBR -> 1 次交换即可到达 RRB（2 个 RB 块集：RB 和 R）
• RBRB-> 1 次交换即可到达 RRBB（2 个完整的 RB 块集）
• RBRBRB-> 2 次交换即可到达 RRRBBB（3 个完整的 RB 块集）
• RBRBRBRB -> 4 个 RB 块集 = 3 次交换

因此，概括来说，所需的交换次数 = N 个 RB 块集（包括不完整的块），并减去 1。

- steve8918

Answer 4

让我们看看你的例子。你知道最终状态将是RRBB或BBRR。换句话说，最终状态总是nRmB或mBnR，其中n是字符串中R的数量，m是B的数量。 由于最终状态已经定义，也许某种路径查找算法会是一个不错的方法？考虑将每个交换视为状态更改，并考虑一种启发式函数来近似剩余所需交换的数量。 我只是随便提出一个想法，但希望这能有所帮助。

- vitorbal

Answer 5

从字符串的右端和左端同时开始两个索引。将左索引向前移动，直到找到一个 R。将右索引向后移动，直到找到一个 B。交换它们。重复此过程，直到左索引遇到右索引，并计算交换次数。然后，进行相同的操作，但在左侧查找 B 并在右侧查找 R。最小值是两个交换计数的较小值。

- Svante

Answer 6

我认为交换次数可以从排序向量所需的逆序数中推导出来。这是使用排列向量执行相同操作的示例。

- Ruslan Kabalin