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

Question

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

写一个函数:

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

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

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

例如，给定 A = [1, 2, 3, 3] 和 B = [1, 3, 4, 3] 应该 返回 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] 你的函数应该返回 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. 形成的子图有两种类型:
   • 里面有一个循环的:在这种情况下，可以证明这个图的每个节点都可以毫无问题地存在于其中一张卡片上。
   • 没有循环的那个:在这种情况下，应该忽略具有最高值的节点，这将允许图中的所有其他节点目前至少出现在一张卡片上上。

由于这将是一个无向图，我们可以使用联合查找算法来解决我们的循环检测问题。由于我更喜欢​​ 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))。