Учитывая два несортированных массива, найдите количество пар, где A [i]> X и B [i]> Y

#algorithm #data-structures

#алгоритм #структуры данных

Вопрос:

Нам даны два несортированных массива. Мы должны найти такое количество пар, чтобы для каждой пары A [i]> X и B [i]> Y. Нам придется обработать 1 миллион таких запросов, где для каждого запроса будут заданы разные значения X и Y. Длина массива также будет составлять до 1 миллиона.

Ограничения :

1 <=A [i],B [i], X,Y <= 10 ^ 9 1<= A.размер, B.размер, количество запросов <= 10 ^ 6

Например :

      A = [7,2,10,15,12,9]
     B = [10,8,5,3,4,7]

Запросы :

       X Y   o/p
      9 3    2  (As we have 2 pairs which satisfy above condition (10,5), (12,4))
      6 4    3  (As we have 3 pairs which satisfy above condition (7,10), (10,5), (9,7))

Есть ли лучший подход, чем грубая сила, поскольку у нас 1 миллион таких запросов?

1. Поиск всех значений в несортированном массиве, которые соответствуют определенному условию, не может быть выполнен лучше, чем за линейное время. Обычно лучшим подходом для ускорения этого процесса является компромисс между пространством и временем путем изменения структуры данных или введения новой, более оптимизированной для поиска

2. Диапазон входного массива?

3. Каков размер X, Y и содержимое A, B? Если они относительно малы, вы можете эффективно выполнить предварительное вычисление.

Ответ №1:

Если запросы предоставляются в автономном режиме, нет необходимости в четырехугольном дереве, и мы можем решить эту O(n log n) проблему. Вставьте все пары запросов и пары массивов в один список, отсортированных по X or a (если an X равно an a , поместите пару запросов после пары массивов). Обработайте пары в списке в порядке убывания ( a или X ). Если это пара массивов, вставьте ее в дерево статистики порядка, упорядоченное по b . Если это запрос, найдите в дереве количество узлов дерева (это пары массивов), которые имеют b > Y (мы уже знаем, что все пары в дереве имеют a > X ).

Ответ №2:

Квадратичное дерево было бы лучше, чем грубая сила. Интерпретируйте пары (a, b) как 2D-координаты точек и вставьте их в квадратичное дерево. Каждый узел в квадродереве также должен хранить свою мощность, то есть количество точек в области, представленной этим узлом. Затем на каждый запрос с подсчетом очков можно ответить рекурсивно в квадродереве, где базовым вариантом является узел, площадь которого либо полностью содержится в пределах области a > X amp;amp; b > Y (в этом случае возвращает мощность узла), либо полностью отделена от него (в этом случае возвращает 0).

Аналогичным образом можно использовать другие подобные структуры данных, такие как k-d дерево.