#algorithm #data-structures
Вопрос:
Я решил эту проблему, используя очередь с максимальным приоритетом. Что я сделал, так это то, что я продолжаю вставлять расстояние, повторяя все возможные пары, пока его размер не станет k. А затем, если я обнаружил, что текущее расстояние больше, чем максимальная вершина кучи, я открываю максимальную кучу и вставляю это расстояние. Затем, после итерации для всех возможных пар, вершина максимальной кучи будет нашим ответом. Временная сложность этого решения, по-видимому, равна O(n^2 logn), а пространственная сложность O(k). Но мне нужно сделать что-то лучше, чем это? Какие могут быть другие подходы?
Ниже приведен снимок кода:
int kthMin(vector<pair<int,int>> Points, int k) {
priority_queue pq;
for(int i=0;i<Points.size()-1; i ) {
for(int j=i 1; j<Points.size(); j ) {
int dist = min( abs(Points[i].first - Points[j].first), abs(Points[i].second - Points[j].second));
if(pq.size()<k) pq.push(dist);
else if(dist< pq.top()) {
pq.pop();
pq.push(dist);
}
}
}
return pq.top();
}
Комментарии:
1. Похоже, что ваш вопрос, если бы в него был включен код, лучше подходил бы для проверки кода , поскольку вы хотите улучшить существующее (рабочее) решение. В его текущем состоянии он на самом деле не подходит ни для одного сайта в сети SE.
2. Отсортируйте все координаты x (помните, к какой точке принадлежит каждая координата). Аналогичным образом отсортируйте все координаты y. Запишите все различия между соседними координатами (если этот набор различий содержит два различия, принадлежащих одной и той же паре точек, пропустите большую). Выполните быстрый выбор для результирующего набора различий.
3. «Но мне нужно сделать что — то лучше, чем это?» — А ты? Почему ты спрашиваешь об этом? Есть ли у вас основания полагать, что вам нужно работать лучше? У вас есть ограничения по размеру/времени? Откуда взялась эта проблема? Есть ли где-нибудь в Интернете более подробная информация и тестирование?
4. Если вы будете следовать подходу грубой силы, найдете расстояние между всеми точками, отсортируете их, выведете k-ю минуту, это займет O(n^2) времени. Если вы хотите повысить сложность, то вы можете использовать двоичный поиск на расстоянии
5. Найдите все расстояния (O(n^2)), затем быстро выберите K-й минимум (O(n)), чтобы общая сложность составляла O(n^2)).
Ответ №1:
Вот более быстрый подход. Насколько быстрее, трудно сказать, я предполагаю, вероятно, что-то вроде O(n^(3/2) log(n)) .
Сначала вставьте все точки в квадратное дерево. Пусть каждый узел квадродерева содержит в качестве метаинформации количество точек в прямоугольнике, а также минимальное и максимальное значения для x и y.
И теперь ваша логика выглядит примерно так.
lower = 0
upper = max(tree.max_x - tree.min_x, tree.max_y - tree.min_y)
while lower < upper:
mid = (lower upper) / 2
max_below = lower
min_above = upper
count_below = 0
count_at = 0
stack = new stack
stack.push((tree, tree)) # To order them,
while stack is not empty:
# We want ordered "pairs of points of interest" meaning
# p1 in tree1, p2 in tree2 and either p1.x < p2.x
# or p1.x = p2.x and p1.y <= p2.y.
(tree1, tree2) = stack.pop()
if no pairs of points of interest (eg tree2.max_x < tree1.min_x):
pass
elsif all of tree1 within distance mid of all of tree2:
count_below = tree1.count * tree2.count
if max_below < max possible distance from tree1 to tree2:
max_below = max possible distance from tree1 to tree2
elsif all of tree1 at distance mid of all of tree2:
count_at = tree1.count * tree2.count
elsif all of tree1 more than distance mid of all of tree2:
if min possible distance from tree1 to tree2 < min_above:
min_above = min possible distance from tree1 to tree2
elsif longest axis of tree1 longer than longest axis of tree2:
for child of tree1:
stack.push((child, tree2))
else:
for child of tree2:
stack.push((tree1, child))
if k < count_below:
upper = max_below
elsif k <= count_below count_at:
return mid
else:
lower = min_above
Идея заключается в том, что ваш двоичный поиск «привязывается» к одному из O(n^2) возможных расстояний. Таким образом, после O(log(n)) логарифмического числа поисков вы найдете правильный. И каждый поиск сам пытается подсчитать числа в блоках, когда это возможно. (В чем помогает структура квадродерева.)
Удачи в том, чтобы сделать этот набросок точным!