Medium

题目描述

给你两个长度为 n 的整数数组 fronts 和 backs，其中第 i 张卡片正面印有正整数 fronts[i]，背面印有正整数 backs[i]。

最初，桌子上每张卡片都正面朝上放置，背面朝下。你可以翻转任意数量的卡片（可能是零张）。

翻转卡片后，如果一个整数在某张卡片的背面朝上，且没有出现在任何卡片的正面朝上，那么这个整数就是好数。

返回翻转卡片后可能的最小好数。如果没有好数，返回 0。

示例 1：

输入：fronts = [1,2,4,4,7], backs = [1,3,4,1,3]
输出：2
解释：
如果翻转第二张卡片，正面朝上的数字是 [1,3,4,4,7]，背面朝上的数字是 [1,2,4,1,3]。
2 是最小的好数，因为它出现在背面但没有出现在正面。
可以证明 2 是翻转一些卡片后可以得到的最小好数。

示例 2：

输入：fronts = [1], backs = [1]
输出：0
解释：
无论如何翻转卡片都没有好数，所以返回 0。

提示：

  • n == fronts.length == backs.length
  • 1 <= n <= 1000
  • 1 <= fronts[i], backs[i] <= 2000

解题思路

这道题的关键在于理解什么是"好数"：一个数字要成为好数，它必须能够通过翻转操作出现在背面，同时不能出现在任何正面。

核心观察：

  1. 如果一张卡片的正面和背面数字相同（如 fronts[i] == backs[i]），那么这个数字永远不可能成为好数，因为无论如何翻转，这个数字都会出现在某张卡片的正面
  2. 对于其他数字，我们需要找到能够出现在背面的最小值

解题思路：

  1. 首先找出所有"坏数"：即正面背面相同的数字，这些数字永远不能成为好数
  2. 收集所有可能的候选数字：所有背面的数字都是潜在的好数
  3. 从候选数字中排除坏数，找到最小值

算法步骤：

  1. 遍历所有卡片，记录正面和背面相同的数字到集合中
  2. 遍历所有背面数字，找到不在"坏数"集合中的最小值
  3. 如果找不到这样的数字，返回0

这个解法的时间复杂度是O(n)，空间复杂度也是O(n)，效率很高。

代码实现

class Solution {
public:
    int flipgame(vector<int>& fronts, vector<int>& backs) {
        unordered_set<int> bad;
        
        // 找出所有正面和背面相同的数字
        for (int i = 0; i < fronts.size(); i++) {
            if (fronts[i] == backs[i]) {
                bad.insert(fronts[i]);
            }
        }
        
        int result = INT_MAX;
        
        // 在所有背面数字中找最小的好数
        for (int back : backs) {
            if (bad.find(back) == bad.end()) {
                result = min(result, back);
            }
        }
        
        return result == INT_MAX ? 0 : result;
    }
};

class Solution:
    def flipgame(self, fronts: List[int], backs: List[int]) -> int:
        # 找出所有正面和背面相同的数字
        bad = set()
        for i in range(len(fronts)):
            if fronts[i] == backs[i]:
                bad.add(fronts[i])
        
        # 在所有背面数字中找最小的好数
        result = float('inf')
        for back in backs:
            if back not in bad:
                result = min(result, back)
        
        return result if result != float('inf') else 0

public class Solution {
    public int Flipgame(int[] fronts, int[] backs) {
        HashSet<int> bad = new HashSet<int>();
        
        // 找出所有正面和背面相同的数字
        for (int i = 0; i < fronts.Length; i++) {
            if (fronts[i] == backs[i]) {
                bad.Add(fronts[i]);
            }
        }
        
        int result = int.MaxValue;
        
        // 在所有背面数字中找最小的好数
        foreach (int back in backs) {
            if (!bad.Contains(back)) {
                result = Math.Min(result, back);
            }
        }
        
        return result == int.MaxValue ? 0 : result;
    }
}

var flipgame = function(fronts, backs) {
    const bad = new Set();
    
    // 找出所有正面和背面相同的数字
    for (let i = 0; i < fronts.length; i++) {
        if (fronts[i]
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(n)需要遍历两次数组，每次遍历时间复杂度为O(n)
空间复杂度O(n)最坏情况下哈希集合需要存储所有不同的数字