MaxNotPresent - переверните несколько карточек, чтобы максимизировать наименьшее целое число, которого нет на лицевой стороне карточки - PullRequest
Новая
       35

MaxNotPresent - переверните несколько карточек, чтобы максимизировать наименьшее целое число, которого нет на лицевой стороне карточки

0 голосов
/ 30 августа 2018

Вы играете в игру с 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]; входные массивы имеют одинаковый размер

Пожалуйста, предоставьте подход к этому вопросу.

1 Ответ

0 голосов
/ 30 августа 2018

Мы можем превратить данную проблему в область теории графов.

  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)).

...