MaxNotPresent- 翻转一些卡片，以最大化任何卡片正面不存在的最小整数

Question

您正在玩 N 张牌的游戏。每张牌的两边都有一个正整数。卡片放在 table 上。游戏的分数是没有出现在正面朝上的牌上的最小正整数。你可以翻转一些卡片。翻转它们后，您可以阅读正面朝上的数字并重新计算分数。你能达到的最高分数是多少？

写一个函数：

class Solution { 
     public int solution(int[] A, int[] B);
}

给定两个整数数组 A 和 B，长度均为 N，分别描述写在卡片两面的数字，分别面向上和向下，returns 是最大可能得分。

例如，给定 A = [1, 2, 4, 3] 和 B = [1, 3, 2, 3]，您的函数应该 return 5，因为在不翻转任何卡片的情况下，从该序列中排除的最小正整数是 5。

例如，给定 A = [1, 2, 3, 3] 和 B = [1, 3, 4, 3] 应该 return 5.

给定 A = [4, 2, 1, 6, 5] 和 B = [3, 2, 1, 7, 7]，你的函数应该 return 4，因为我们可以翻开第一张牌，让数字朝上是 [3, 2, 1, 6 , 5] 而且数字3和4不可能都朝上.

给定 A = [2, 3] 和 B = [2, 3] 你的函数应该 return 1，因为无论卡片如何翻转，面朝上的数字都是 [2, 3].

为以下假设编写一个有效的算法：

N 是 [1..100,000]; 范围内的整数数组A、B的每个元素都是[1..100,000,000];范围内的整数输入数组大小相等

请提供解决此问题的方法。

Answer 1

我们可以将给定的问题转化为图论领域。

将每一个(A[i], B[i])对视为节点A[i]和节点B[i]之间的一条边
这将依次创建许多不相交的子图。
形成的子图有两种类型：
- 里面有环的那个：在这种情况下可以证明这个图的每个节点都可以毫无问题地存在于其中一张卡片上。
- 没有循环的那个：在这种情况下，应将具有最高值的节点排除在外，这将允许图中的所有其他节点目前至少在其中一个节点上卡面朝上。

由于是无向图，我们可以使用并查算法来解决我们的环检测问题。因为我更喜欢 C++，这里有一个伪代码：

map<int, int> parent; // default value is 0
map<int, bool> isCyclic; // default value as false
map<int, int> maxValue; // default value as 0

int find(int x) {
    if(parent[x] == x) return x;
    parent[x] = find(parent[x]);
    return parent[x];
}

void join(int x, int y) {
    int parent_x = find(x);
    int parent_y = find(y);

    if(parent_x == parent_y) {
        isCyclic[parent_x] = true;
        return;
    }

    maxValue[parent_y] = max(maxValue[parent_x], maxValue[parent_y]);
    isCyclic[parent_y] = (isCyclic[parent_x] || isCyclic[parent_y]);
    parent[parent_x] = parent_y;
}


int solve(vector<int> A, vector<int> B) {
    int n = A.size();

    for(int i = 0; i < n; i++) {
        if(parent[A[i]] == 0) parent[A[i]] = A[i];
        if(parent[B[i]] == 0) parent[B[i]] = B[i];

        join(A[i], B[i]);
    }

    set<int> maxValues;
    for(pair<int,int> keyValue : parent) {
        // store the max values of each group in a set
        int group = find(keyValue.first);
        maxValues.insert(maxValue[group]);
    }

    for(int i = 1; i <= n; i++) {
        int group = find(i);
        if(isCyclic[group]) continue;
        if(maxValues.find(i) == maxValues.end()) return i;
    }

    return n + 1;
}

解决方案的总运行时复杂度为 O(n*log(n))。

MaxNotPresent- 翻转一些卡片，以最大化任何卡片正面不存在的最小整数

MaxNotPresent- Flip some cards over so as to maximize the smallest integer that's not present on any card's front

arrays

sorting

algorithm

search

maximize