Подсчет инверсий 2D-пары (x, y) в списке

#python #inversion

#python #инверсия

Вопрос:

Вопрос похож на обычный вопрос об инверсии подсчета, но вместо списка одиночных чисел теперь вводится список пар (x, y).

Для списка пар [(x1,y1),(x2,y2),(x3,y3), …,(xn, yn)] пара (i, j) является инверсией i < j , если и xi>xj , yi>yj . Возможно ли написать алгоритм в O (n logn logn)? Я пробовал несколько способов, но на этапе слияния каждый элемент из правой половины списка должен сравниваться со всеми элементами в левой, что приводит к временной сложности в n квадратов.

1. Если это тот же вопрос, но только с парами int вместо int , почему стандартный алгоритм потерпит неудачу?

2. @Abhinav Mathur Стандартный алгоритм работает, но со сложностью в N квадратов. B / c для каждого шага слияния и подсчета вам нужно сравнить a (xj, yj) из правой части со всеми (xi, yi) из левой части. Но я хочу иметь решение со сложностью O (nlonlogn)

Ответ №1:

Разделите список на две половины left и right на основе x координаты. Затем сравните самую низкую точку двух половин (на основе их y координат). Есть два случая:

Левая точка ниже правой точки, тогда левая точка имеет xi<xj и yi<yj для всех точек справа от нее.
Правая точка ниже левой, поэтому yi>yj условие выполняется для любой точки слева от нее.
После обновления вашего ответа в соответствии с этими 2 случаями вы можете удалить один из этих двух пунктов и продолжить работу с оставшимися отсортированными списками (рекурсивно решая для left и right также). Это должно работать в O(nlog^2n)

1. Абинав, спасибо за ответ! Только одна быстрая проблема. Когда вы разделяете исходный список на две половины, то есть на левую и правую, на основе значений x, это нарушит порядок в исходном списке, верно? И, таким образом, когда вы сопоставили левую точку (xi) с правой точкой (xj), нет никакой гарантии, что i < j b / c теперь i,j из отсортированного списка вместо исходного списка.

2. В вопросе вы ничего не упомянули о заказе на (i,j)

3. Sry, мой плохой: ( Я обновлю описание. Требование такое же, как и при стандартном подсчете инверсии. индекс (i, j) называется инверсией, если i<j и xi> xj, yi> yj.

4. Где размещен этот вопрос? Я почти уверен, что вопрос не будет запрашивать i<j условие

5. Это бонусный вопрос из домашней работы CS. Но, возможно, он может использовать знания half-inverted , которые взяты из предыдущей части того же списка вопросов. Определяется half-inverted pair как: With a fixed constant y0 a pair (i,j) is called half-inverted if i < j, xi > xj, and yi >= y0 > yj