:-: 2.3 翻转卡片游戏 ***** **题干：** 在桌子上有 N 张卡片，每张卡片的正面和背面都写着一个正数（正面与背面上的数有可能不一样）。我们可以先翻转任意张卡片，然后选择其中一张卡片。如果选中的那张卡片背面的数字 X 与任意一张卡片的正面的数字都不同，那么这个数字是我们想要的数字。哪个数是这些想要的数字中最小的数（找到这些数中的最小值）呢？如果没有一个数字符合要求的，输出 0。 其中, fronts[i] 和 backs[i] 分别代表第 i 张卡片的正面和背面的数字。如果我们通过翻转卡片来交换正面与背面上的数，那么当初在正面的数就变成背面的数，背面的数就变成正面的数。 示例： ``` 输入：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 就是我们想要的数字。 提示： ``` 1 <= fronts.length == backs.length <= 1000 1 <= fronts[i] <= 2000 1 <= backs[i] <= 2000 ``` **题目分析：** 题目的意思是每张卡片都有被翻转的可能，而且题目要求是我们选择的那一张卡片背后的数字与所有卡片正面的数字都不相同。并找出符合这个条件的最小数字。 此题核心可用一句话概括：**假作真时真亦假，无为有处有还无** 首先我们来分析那些明显不符合条件的卡牌数字：正面与反面数字相同，无论你怎么翻转，符合条件的数字都不可能是这个卡牌上的数字。 接着我们来找符合条件的数字：我们先要理解这个“先翻转任意张卡片”的意思，它的是每张卡片都有被翻转的可能，但是这并不是让我们用代码来列出所有的可能，如果要这样做，2000多张牌要排列到何时？它只是要告诉我们每一张卡片的背面数字都有可能成为正面数字，每一个正面数字都有可能成为背面数字，所以背面数字和正面数字的界限就被打破了，它们没有了界面之分，于是我们只要在排除了不可能情况的数字条件下的所有卡牌数字中找出最小值即可。哪怕这个最小值原先在正面，翻转不就到反面了吗？ **新手有可能遇到的解题思路陷阱：** 陷入翻转任意张卡片的陷阱中，进行每次组合排列，列出所有的翻转情况，这种无疑是难以实现的。 **解题思路分析以及代码实现：** 第一种思路：用哈希表或者其他的集合，数组等存储正面和背面都一样的数字，然后对于不在此哈希表或者其他的集合，数组等中出现的所有数字，找出其最小值。 第一种思路代码： ``` public int flipgame(int[] fronts, int[] backs) { int min = Integer.MAX_VALUE; int min = Integer.MAX_VALUE; Map<Integer, Integer> map = new HashMap<Integer, Integer>(); for (int i = 0; i < fronts.length; i++) { if (fronts[i] == backs[i]) { map.put(fronts[i], backs[i]); } } for (int i = 0; i < fronts.length; i++) { if (!map.containsKey(fronts[i])) { min = Math.min(min, fronts[i]); } if (!map.containsKey(backs[i])) { min = Math.min(min, backs[i]); } } // return min % Integer.MAX_VALUE; return min == Integer.MAX_VALUE ? 0 : min; } ``` **复杂度分析** 时间复杂度：O(n)。 空间复杂度：O(n)。 第二种思路：使用TreeSet集合，将卡牌的正面和背面数字都存储进去，然后删除掉正面和背面数字一样的卡牌上填写的数字（只要和正面和背面数字都一样的卡牌上的数字一样，都删除掉），然后在判断集合是否为空（都不符合则集合为空），为空返回零，不为空返回第一项。 为什么选用TreeSet?主要是两个原因：Set集合值不重复，TreeSet有序。 可以参考这个博客：[Java Set集合详解](https://blog.csdn.net/qq_33642117/article/details/52040345) 在这个算法中还有很多其他的解题思路，大多都大同小异，自己发挥一下吧。 第二种思路代码： ``` public static int flipgame(int[] fronts, int[] backs) { int min = Integer.MAX_VALUE; Set<Integer> set = new TreeSet<Integer>(); //TreeSet<Integer> set = new TreeSet<>(); for (int i = 0; i < fronts.length; i++) { set.add(fronts[i]); set.add(backs[i]); } for (int i = 0; i < fronts.length; i++) { if (fronts[i] == backs[i]) { set.remove(fronts[i]); } } min = set.isEmpty() ? 0 : set.iterator().next().intValue(); //min = set.isEmpty() ? 0 : set.first(); return min; } ``` **复杂度分析** 时间复杂度：O(n)。 空间复杂度：O(n)。 **若有理解错误的、写错的地方、更好的思路，方法，望各位读者评论或者发邮件指正或指点我，不胜感激。**