arrays - 给定一串红色和蓝色的球，找到将颜色组合在一起的最小交换次数

Question

我们得到一个形式为 RBBR 的字符串，其中 R - 红色，B - 蓝色。

我们需要找到将颜色组合在一起所需的最少交换次数。在上述情况下，答案将是 1 以获得 RRBB 或 BBRR。

我觉得对部分排序的数组进行排序的算法在这里会很有用，因为简单的排序会为我们提供交换次数，但我们需要 最小 交换次数。

有什么想法吗？

根据 this，这据称是 Microsoft 面试问题.

Answer 1

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