Как, используя алгоритм быстрой сортировки, определить лежит точка в массиве отрезков или нет?
Доброго всем дня.
Прохожу курс по алгоритмам и одно из заданий таково:
Даны отрезки вида [x, y], где x - координата начала отрезка, а у, соответственно, координата конца. Также дан массив точек [x1, x2, x3, ... , xn]. Необходимо определить в каком количестве отрезков содержится каждая точка. Задание находится в теме "Быстрая сортировка" и очевидно, что использовать нужно её, но я не понимаю, с чего нужно начинать.
Наивный алгоритм за O(n^2) ясен, для каждой точки пробегаемся по всем возможным отрезкам.
Далее приведу свои дальнейшие рассуждения по прикручиванию быстрой сортировки:
1. Сортировать массив точек не имеет смысла, так как выдавать результат по каждой точке необходимо в порядке появления её в потоке ввода.
2. Объединять все массивы отрезков в один также не имеет смысла, потому что тогда мы не сможем контролировать начало и конец отрезка, так как все смешается в упорядоченную кашу.
3. Создать два массива для начал и концов отрезков ( 1: [x1, x2, x3, ... , xn], 2: [y1, y2, y3, ... , yn]
Отсортировать их с помощью "быстрой" сортировки (используя тройное разделение для ускорения сортировки повторяющихся элементов) и...
Что делать дальше мне не совсем понятно. Просто последовательно проходить по упорядоченным массивам [x] и [y] для каждой точки, тем самым получив число отрезков, в которые точка входит или как?
Можно решить и за линейное время (после сортировок):
1) берём массив концов отрезков (xi,1) и (yi,-1), сортируем (не забывая, что при одинаковых первых числах сначала идут все начала отрезков, а потом все концы: так для отрезков [1,2] и [2,3] получим массив (1,1),(2,1),(2,-1),(3,-1))
2) берём массив длиной n (число точек), заполняем его числами от 1 до n (если пишем на C-подобных языках - то от 0 до n-1). Cортируем массив, используя условие less(a,b)=(P[a] < P[b]), где P - массив точек. Получим индексы точек, отсортированные по возрастанию координат соответствующих точек.
3) Идём по обоим массивам, сравниваем координаты. Когда проходим точку в массиве концов, то прибавляем к счётчику второй элемент. Когда достигаем координаты очередной точки из P - записываем в массив результатов значение счётчика. Не забываем, что точка P[a]=x обрабатывается после всех точек (x,1) но до всех точек (x,-1) из массива концов.
4) Выводим массив результатов.
А проще всего код получается, если искомые точки сложить в тот же массив, что и концы отрезков (со вторым числом 0 и третьим - индексом точки) и отсортировать всю кучу. Можно уложиться в один экран на C :)
Объединить вместе в один массив точки начал (с доп.полем "+1") и концов (с доп.полем "-1") отрезков и отсортировать его по координате : [11,+1],[17,+1],[21,-1],[32,+1],[37,-1],[42,-1]
А затем один раз пройтись по нему накапливая сумму доп.поля.
Спасибо за ответ. То есть для каждой точки нужно будет пройтись по данному массиву? То есть в вашем примере, пока координата входной точки больше координаты отрезков, мы идем по массиву и суммируем поля?
На мой взгляд, можно один раз сформировать подобный массив, затем преобразовать его к виду [11,1],[17,2],[21,1],[32,2],[37,1],[42,0], где координате соответствует, на скольких отрезках лежат точки с координатой больше заданной (но меньше следующей координаты, в примере точки с значением координаты от 11 до 17 лежат на одном отрезке, от 17 до 21 - на двух и т.д.). Затем преобразовать массив в дерево поиска, тогда, если не ошибаюсь, для m точек и n отрезков время будет составлять в среднем O(mlogn).
@throughtheether не кажется ли вам, что построение подобного массива займет время O(n^2)? Тем более что точка со значением координаты от 11 до 17, может лежать и на большем количестве отрезков (например даны отрезки [11, 17], [11, 21], [11, 18] и т.д.).
не кажется ли вам, что построение подобного массива займет время O(n^2)?
Не думаю. Пробегаем по массиву вида [11,+1],[17,+1],[21,-1],[32,+1],[37,-1],[42,-1], аккумулируем ассоциированные с координатами значения (+1,-1) и присваиваем значение аккумулятора текущему элементу (в этой же итерации). На мой взгляд, здесь все линейно.
Тем более что точка со значением координаты от 11 до 17, может лежать и на большем количестве отрезков (например даны отрезки [11, 17], [11, 21], [11, 18] и т.д.).
На мой взгляд, эту проблему можно решить в линейное время. Пробегая по всем концам отрезков (O(2n)), увеличиваем/уменьшаем соответствующее значение для каждой координаты. То есть, в разных итерациях координате 11 будет соответствовать +1, координате 17-> -1, затем 11-> +2, 21-> -1, 11-> +3, 18->-1. Результирующие элементы будут иметь вид [11,+3],[17,-1],[18,-1],[21,-1].
