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

Question

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

写一个函数：

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

在给定两个整数A和B的数组的情况下，长度为N，描述分别面朝上和朝下写在卡片两侧的数字，返回最大可能分数。

例如，给定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]，你的函数应该返回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

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

1. 将每个（A [i]，B [i]）对视为节点A [i]和节点B [i]之间的边缘
2. 这将反过来创建一些不相交的子图。
3. 形成的子图有两种类型： 内部循环的那个：在这种情况下，可以证明该图的每个节点都可以存在于其中一个卡上而没有任何问题。 没有循环的那个：在这种情况下，应该省略具有最高值的节点，这将允许图中的所有其他节点在至少一个面朝上的卡上存在。

由于它将是一个无向图，我们可以使用union-find算法来解决我们的循环检测问题。因为我更像是一个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））。