Решить проблему с O (nlogn) время

Question

Пусть A [1] <= A [2] <= .... <= A [n].Пусть X - произвольное число.Дайте алгоритму найти все пары A [i] и A [j] такие, что A [j] - A [i]> = X. Все числа являются натуральными числами.

Если вы хотите увидеть исходную проблему.Вот оно:

Пусть P = {p1;p2;;pn} будет набором из n точек в 2-мерном пространстве, где pi = (xi; yi) для каждого i.Пусть D = (dx; dy).Задача состоит в том, чтобы решить, существует ли пара точек pi и pj такая, что xj - xi> = dx и yj - yi> = dy.Вы можете легко решить эту проблему за O (n ^ 2) раз, рассмотрев все возможные пары точек.Но мы заинтересованы в разработке алгоритма времени O (n log n).

Answer 1

Здесь вы можете воспользоваться тем, что ваши входные данные отсортированы и все числа являются положительными целыми числами. Если

A[j] - A[i] ≥ X

тогда мы знаем, что следующее также верно

A[j + 1] - A[i] ≥ X

Так что алгоритм может быть

for(i = 1; i < n; i++) // for every value (this part is O(n))
{
    int minJ = A[i] + X; // the minimum J that satisfies `A[j] - A[i] >= X`

    int cutoff = binarySearch(minJ); // figure out the minimum J for which  `A[j] - A[i] >= X` (this part is O(log(n))

    storeResults(i, cutoff, n); // In Answers[i], save every qualifying integer (this part is less than O(log(n))
}

Всего у вас есть

O (n * (log (n) + меньше чем log (n))
O (n * (2 log (n)))
O (n * log (n))

Есть место для некоторых незначительных оптимизаций, таких как выполнение только основного цикла до n - 1 вместо n, но это на самом деле не критично или не имеет отношения к Big-Oh.

Answer 2

Очевидно, что max(A[j] - A[i]) достигается, когда A[j] является наибольшим, а A[i] наименьшим: A[n] - A[1].Таким образом, вам просто нужно проверить i = n и j = 1.O(1):)

edit
Если вам нужно найти все такие пары (i, j), тогда, очевидно, это задача O(n^2): потому что есть O(n^2) решенийобщий случай.Итак, просто проверьте все пары.

for (int i = 0; i < n; ++i) {
    for (int j = 0; j < n && A[i] - A[j] >= X; ++j) {
        if (i != j) {
            print("new pair: ", i, j);
        }
    }
}

Answer 3

Может быть, я очень плохо разбил пробу, но теперь я получил ответ на оригинал.Вот мое решение:

Шаг 1: Сортировать множество P по координате x.

Шаг 2: Пусть Q = {q1, q2, ..., q_n}, где qi = min{y1, y2, .., y_i}

Шаг 3: Если (x_n - x_midpoint> = dx)

      if(y_n - q_midpoint >= dy)

        return there exit;

      else repeat step3 for x_n and the new midpoint of the range after the midpoint

   else

       repeat step 3 for x_n and the new midpoint of the range from the midpoint to the left.

       When there is only one element in the range and the pair hasn't been found, repeat Step 3 for x_n-1, x_n-2,..., x2. 

       If the pair hasn't been found after this, then there exist no such pair.

Простите всех, если мой первый вопрос не имеет смысла!

Answer 4

Я думаю, что получил, но так как это пахнет домашней работой, я просто дам подсказку. Мой алгоритм использует список точек, который всегда упорядочен так, что x увеличивается, а y уменьшается. Точки считаются по одной за раз, и каждая точка попадает в один из четырех случаев:

1. Найдена пара точек, удовлетворяющих условию.
2. Мы можем доказать, что можно игнорировать новую точку без ложного утверждения, что ответов нет.
3. Новая точка вставляется в список, сохраняя инвариант о его упорядочении.
4. Новая точка заменяет одну или несколько точек, которые были ранее в списке, и мы можем доказать, что удаляемые точки можно безопасно игнорировать.

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

Answer 5

Вы пытаетесь найти пары чисел A [j] - A [i]> = X.

Это должно быть возможно примерно за 2 часа:

Для каждого числа (порядок n)
Выполните двоичный поиск (logn), чтобы найти последнее число, которое соответствует критериям A [j] - A [i]
Распечатать все числа перед ним (n)

В коде псевдо:

for(int i = n; i > 0; i--) // O(n)
{
   int last_number = binarySearch(i); // O(log (n/2)) because on avg we only need to search half the list
   if(last_number != SOME_INVALID_THING)
   {
      for(int x = 0; x < last_number; x++) // O(n)
      {
         printf("%d %d", i, x);
      }
   }
}

Это правильно?Или это просто n ^ 2, кажется, что вы никогда не будете выполнять большую работу, но вложенные циклы подразумевают n ^ 2.

Answer 6

С хорошей структурой данных это можно сделать за O (n)

Поместите А в связанный список.

Создать еще один связанный список со ссылками на A [i] и A [j].

Теперь мы можем начать.

Ai = Aj = first element of A
while Aj <> null
    if Aj - Ai < X 
    then 
        Aj = Aj.next
    else
        S.ai = Ai
        S.aj = Aj
        Ai = Ai.next
    end 
end

есть один цикл, и Aj будет продвигаться между 50% и 100% случаев в зависимости от X. Из-за связанных списков мы избегаем взрыва копий.

==> O (N)

С добавлением исходной задачи к двумерной задаче внесены некоторые изменения, индекс должен быть сохранен со значением.

есть 2 списка с элементами xi -> xk и yi -> yl (где xk и yl - наименьшие числа> = xi + dx и соответственно yi + dy.

Если вы найдете пару xi, yi, где k - l имеет знак, отличный от предыдущих i, вы можете пройти по списку xj или yj, чтобы найти точку, которая удовлетворяет ограничению.

Answer 7

Меня смущает, почему это не проблема O (n): просто переберите значения с индексом i и позвольте другому индексу j отстать, чтобы он всегда был на уровне или раньше значения назадв списке, значение которого как минимум X меньше текущего A[i].Для каждого значения A[i] загляните назад на A[j] и посмотрите, является ли разница точно X, и если да, то запомните эту пару i,j.Затем продвиньтесь j, если необходимо, чтобы A[j+1] находился в пределах X от A[i], и вернитесь к вершине цикла.

Редактировать: Никита РыбакСовершенно верно, что я пропустил> = в задаче, но это только значительно упрощает задачу: вместо сопоставления значений j для данного i, являющегося диапазоном с остановом и началом, все, что нам нужно, это одинграницу, потому что если, например, A[6] - A[4] >= X, то, очевидно, то же самое будет справедливо для A[6] и всего, начиная с A[3] и далее.

Answer 8

Поскольку вход отсортирован, вы можете двоично искать X - A[i] для каждого i от 1 до n. Поскольку элементы могут быть равны, вам нужно найти верхнюю и нижнюю границы для бинарного поиска. Я думаю, что это будет O (nlogn) ...