Блог

Я пытался решить следующую проблему. У меня есть последовательность натуральных чисел, которая может быть очень длинной (несколько миллионов элементов). Эта последовательность может содержать «скачки» в значениях элементов. Вышеупомянутый переход означает, что два последовательных элемента отличаются друг от друга более чем на 1.

Пример 01:

1 2 3 4 5 6 7 0

В вышеупомянутом примере происходит переход между 7 и 0.

Я искал какой-нибудь эффективный алгоритм (с точки зрения времени) для определения положения, в котором происходит этот скачок. Эта проблема осложняется тем фактом, что может возникнуть ситуация, когда присутствуют два прыжка, и один из них — это прыжок, который я ищу, а другой — обтекание, которое я не ищу.

Пример 02:

9 1 2 3 4 6 7 8

Здесь первый переход между 9 и 1 является окончательным. Второй прыжок между 4 и 6 — это тот прыжок, который я ищу.

Моя идея состоит в том, чтобы каким-то образом модифицировать алгоритм двоичного поиска, но я не уверен, возможно ли это из-за присутствия обхода. Стоит сказать, что максимум могут произойти только два перехода, и между этими переходами элементы сортируются. У кого-нибудь есть какие-нибудь идеи? Заранее спасибо за любые предложения.

Вы не можете найти эффективное решение (эффективное означает, что не смотрите на все числа, O (n)), поскольку вы не можете сделать никаких выводов о своих числах, просмотрев меньше, чем все. Например, если вы смотрите только на каждое второе число (все еще O (n), но с более высоким коэффициентом), вы бы пропустили двойные переходы, подобные этим: 1 5 3 . Вы можете и должны просмотреть каждое отдельное число и сравнить его с соседними. Вы могли бы разделить свою рабочую нагрузку и использовать многоядерный подход, но не более того.

Обновить

Если у вас есть особый случай, когда в вашем списке есть только 1 переход, а остальные отсортированы (например. 1 2 3 7 8 9 ), вы можете найти этот переход довольно эффективно. Вы не можете использовать ванильный двоичный поиск, поскольку список может быть отсортирован не полностью, и вы не знаете, какое число вы ищете, но вы могли бы использовать сокращение от экспоненциального поиска, которое имеет некоторое сходство.

Для работы этого алгоритма нам нужны следующие допущения:

• Существует только 1 переход (я игнорирую «обтекание перехода», поскольку технически он не находится ни между какими следующими элементами)
• Список отсортирован иным образом, и он строго монотонно увеличивается

С этими допущениями мы сейчас в основном ищем прерывание в нашей монотонности. Это означает, что мы ищем случай, когда 2 элемента и b имеют n элементов между ними, но не удовлетворяют b = a n . Это должно быть верно, если между двумя элементами нет перехода. Теперь вам нужно только найти элементы, которые не выполняют это нелинейным образом, отсюда и экспоненциальный подход. Этот псевдокод мог бы быть таким алгоритмом:

 let numbers be an array of length n fulfilling our assumptions

start = 0
stepsize = 1
while (start < n-1)
    while (start   stepsize > n)
        stepsize -= 1
    stop = start   stepsize
    while (numbers[stop] != numbers[start]   stepsize)
        // the number must be between start and stop
        if(stepsize == 1)
            // congratiulations the jump is at start to start   1
            return start
        else
            stepsize /= 2
    start  = stepsize
    stepsize *= 2

no jump found