Для двух несортированных массивов найдите количество пар, в которых A[i] > X и B[i] > Y
Нам даны два несортированных массива. Нам нужно найти такое количество пар, что для каждой пары A[i] > X и B[i] > Y. Нам нужно будет обработать 1 миллион таких запросов, где в каждом запросе будут заданы разные X и Y. Длина массива также будет до 1 миллиона.
Ограничения:
1 <=A[i],B[i],X,Y <=10^9 1<= A.size, B.size, количество запросов <= 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 миллион таких запросов?
Диапазон входного массива?
Каков размер X, Y и содержимое A, B? Если они относительно малы, вы можете эффективно выполнять предварительные вычисления.
Ответы 2
дерево квадрантов было бы лучше, чем грубая сила. Интерпретируйте пары (a, b) как двумерные координаты точек и вставьте их в дерево квадрантов. Каждый узел в дереве квадрантов также должен хранить свою мощность, т. е. количество точек в пределах области, представленной этим узлом. Затем на каждый запрос подсчета точек можно ответить рекурсивно в дереве квадрантов, где базовым случаем является узел, площадь которого либо полностью содержится в регионе a > X && b > Y (в этом случае возвращается мощность узла), либо полностью не пересекается с ним (в этом случае вернуть 0).
Аналогичным образом можно использовать и другие подобные структуры данных, такие как дерево k-d.
Если запросы предоставляются в автономном режиме, в дереве квадрантов нет необходимости, и мы можем решить это в O(n log n). Вставьте все пары-запросы и пары-массивы в один список, отсортированный по X или a (если X равно a, поместите пару запросов после пары массивов). Обработайте пары в списке в порядке убывания (из a или X). Если это пара массивов, вставьте их в дерево статистики порядка, упорядоченное по b. Если это запрос, найдите в дереве количество узлов дерева (это пары массивов), которые имеют b > Y (мы уже знаем, что все пары в дереве имеют a > X).
Не могли бы вы рассказать подробнее о дереве статистики заказов?
@Bhargavkular, пожалуйста, смотрите https://en.wikipedia.org/wiki/Order_statistic_tree
Поиск всех значений в несортированном массиве, соответствующих определенному условию, невозможно выполнить быстрее, чем за линейное время. Обычно лучшим подходом к ускорению этого является компромисс между пространством и временем путем изменения структуры данных или введения новой, более оптимизированной для поиска.