9.1练习题2 硬币翻转 题解

这道题可以用贪心算法来解决。

假设有 $n$ 枚硬币，我们可以把它们分成两组，一组是正面朝上的硬币，一组是正面朝下的硬币。如果其中一组的数量超过了 $n/2$，那么我们只需要把另外一组全部翻转过来，就可以使得正面朝上的硬币数量超过了 $n/2$。

因此，我们只需要统计正面朝上和正面朝下的硬币数量，然后取数量较少的一组进行翻转，就可以满足要求。

具体实现可以参考以下代码：

def flip_coins(coins):
    n = len(coins)
    heads = sum(coins)
    tails = n - heads
    if heads > tails:
        coins = [1-x for x in coins]  # 翻转所有硬币
    return coins

这个算法的时间复杂度是 $O(n)$，其中 $n$ 是硬币的数量。