Проверьте, совпадает ли набор первых элементов X одного массива с набором первых элементов Y другого

Даны два массива arr1[] и arr2[] размера N каждый и массив Q[][2] , состоящий из M запросов вида [x, y], задача для каждого запроса состоит в том, чтобы проверить, содержит ли набор значений из первых x элементов arr1[] равно набору значений из первых y элементов arr2[] .

Примечание. Два множества равны, если все их различные элементы равны. Например, {1, 2, 2, } и {1, 2} являются одинаковыми множествами, а {1, 2, 3} и {1, 3} — нет.

Примеры:

Input: arr1[] = {5, 6, 7, 8, 9}, arr2[] = {5, 6, 6, 8, 7}, Q[][] = {{4, 5}, {3, 3}, {2, 3}}
Output: 
YES
NO
YES
Explanation: 
Query 1:  [4, 5] first 4 elements of arr1[] are A = {5, 6, 7, 8} and the first 5 elements of arr2[] are B = {5, 6, 6, 8, 7} since the distinct elements in both of the sets A and B are equal. Hence print “YES“.
Query 2:  [3, 3] first 3 elements of arr1[] are A = {5, 6, 7} and the first 3 elements of arr2[] are B = {5, 6, 6} since the distinct elements in both of the sets A and B are not equal. Hence print “NO“.
Query 3:  [2, 3] first 2 elements of arr1[] are A = {5, 6} and the first 3 elements of arr2[] are B = {5, 6, 6} since the distinct elements in both of the sets A and B are equal. Hence print “YES”.

Input: arr1[] = {1, 2, 2, 3}, arr2[] = {1, 3, 2, 2}, Q[][] = {{2, 2}, {4, 3}, {4, 4}}
Output: 
NO
YES
YES

Наивный подход: основной способ решения проблемы заключается в следующем:

For each query, we will maintain two sets and we will traverse and insert the first x elements of arr1[] and the first y elements of arr2[]. Then equate these sets and check if they are equal.

Ниже приведена реализация описанного выше подхода.

Временная сложность: O(N * M)
Вспомогательное пространство: O(N * M)

Эффективный подход. Описанный выше подход может быть оптимизирован на основе следующей идеи:

This problem can be solved using Zobrist Hash, which is a probabilistic algorithm to determine if two sets are equal. 

In Zobrist Hash we assign random value to each number then check whether their XOR equal or not. We will use Zobrist Hash with prefix XOR array to be able to tell xor of first N elements in constant time for each query. if XOR of the first X element of arr1[] is equal to XOR of first Y elements of arr2[]then they are same set so print “YES” else “NO“.

Выполните следующие шаги, чтобы решить проблему:

• Создание массивов PrefixXOR pre1[] и pre2[] для arr1[] и arr2[] для предварительного вычисления XOR первых n различных элементов
• Объявление двух наборов для arr1[] и arr2[] . Как только мы возьмем Xor элемента x , мы поместим его в эти наборы, чтобы избежать повторного использования xor того же элемента.
• Объявить хеш-карту numberGenerated для хранения сгенерированных случайных чисел. Таким образом, каждое число будет иметь уникальное случайное число.
• Предварительно вычислить массив префиксов xor для arr1[] и arr2[] .
• Для каждого запроса сохраните xor первых элементов X в xorOfFirstX и xor первых элементов Y в xorOfFirstY .
• Если они равны, выведите «YES» , иначе выведите «NO» .

Ниже приведена реализация описанного выше подхода.

Временная сложность: O(N*logN + M)
Вспомогательное пространство: O(N)

Статьи по Теме:

• Введение в массивы - учебные пособия по структурам данных и алгоритмам
• Введение в хэширование — учебные пособия по структурам данных и алгоритмам