43 lines
1.4 KiB
Markdown
43 lines
1.4 KiB
Markdown
方法一：哈希集
|
||
思路与算法
|
||
|
||
如果一张卡片正反两面有相同的数字，那么这张卡片无论怎么翻转，正面都是这个数字，这个数字即不能是最后所选的数字 xxx。
|
||
|
||
按照这个思路，我们首先遍历所有卡片，如果卡片上的两个数字相同，则加入哈希集合 same\textit{same}same 中，除此集合外的所有数字，都可以被选做 xxx， 我们只需要再次遍历所有数字，找到最小值即可。
|
||
|
||
最后，我们返回找到的最小值，如果没有则返回 000。
|
||
|
||
代码
|
||
|
||
```js
|
||
var flipgame = function(fronts, backs) {
|
||
const same = new Set();
|
||
for (let i = 0; i < fronts.length; i++) {
|
||
if (fronts[i] === backs[i]) {
|
||
same.add(fronts[i]);
|
||
}
|
||
}
|
||
let res = 3000;
|
||
for (let x of fronts) {
|
||
if (x < res && !same.has(x)) {
|
||
res = x;
|
||
}
|
||
}
|
||
for (let x of backs) {
|
||
if (x < res && !same.has(x)) {
|
||
res = x;
|
||
}
|
||
}
|
||
return res % 3000;
|
||
};
|
||
```
|
||
复杂度分析
|
||
|
||
时间复杂度：O(n)O(n)O(n)，其中 nnn 是卡片个数。
|
||
|
||
空间复杂度：O(n)O(n)O(n)，其中 nnn 是卡片个数。
|
||
|
||
作者：力扣官方题解
|
||
链接：https://leetcode.cn/problems/card-flipping-game/solutions/2365854/fan-zhuan-qia-pian-you-xi-by-leetcode-so-acbj/
|
||
来源：力扣（LeetCode）
|
||
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。 |