Найти триплеты лучше, чем линейное, так что A [n-1] >= A [n] <= A [n + 1]

Ответ 1

Мы можем решить это в O(logn) время, используя divide и завоевать aka. двоичный поиск. Лучше, чем линейное время. Поэтому нам нужно найти триплет такой, что A[n-1] >= A[n] <= A[n+1].

Сначала найдите середину данного массива. Если середина меньше ее левой и больше ее правой. затем верните, вот ваш ответ. Кстати, это было бы базой в вашей рекурсии. Также, если len(arr) < 3, то тоже возвращаются. другой базой.

Теперь идут сценарии рекурсии. Когда нужно возвращаться, нам нужно будет проверить дальше. Для этого, если середина больше элемента слева от нее, рассмотрим начало слева от массива как подзадачу и рекурсию с этим новым массивом. т.е. в материальных терминах в этой точке мы имели бы ...2 6 ... с индексом n равным 6. Поэтому мы перемещаем влево, чтобы увидеть, находится ли элемент слева от 2 триплет.

В противном случае, если середина больше элемента в своем правом подмассиве, тогда рассмотрите середину + 1 справа от массива в качестве подзадачи и рекурсии.

Подробнее Теория: вышеизложенного должно быть достаточно, чтобы понять проблему, но читать дальше. Проблема в основном сводится к поиску локальных минимумов в заданном наборе элементов. Число в массиве называется локальным минимумом, если оно меньше, чем его левое и правое числа, которые точно сводятся к A[n-1] >= A[n] <= A[n+1].

Данный массив, такой, что его первые 2 элемента уменьшаются, а последние 2 элемента увеличиваются, чтобы иметь локальные минимумы. Почему это? Докажем это отрицанием. Если первые два числа уменьшаются, а локальных минимумов нет, это означает, что 3-е число меньше 2-го числа. в противном случае вторым номером были бы локальные минимумы. По той же логике 4-й номер должен быть меньше 3-го числа и т.д. И т.д. Поэтому числа в массиве должны быть в порядке убывания. Который нарушает ограничение последних двух чисел в порядке возрастания. Это доказывает отрицание того, что должны быть локальные минимумы.

Вышеупомянутая теория предполагает линейный подход O(n), но мы определенно можем сделать лучше. Но теория определенно дает нам другую точку зрения на проблему.

Код: Здесь код python (fyi - был введен в текстовый редактор stackoverflow в обратном порядке, он может ошибочно ошибаться).

def local_minima(arr, start, end):
    mid = (start+end)/2

    if mid-2 < 0 and mid+1 >= len(arr):
        return -1;

    if arr[mid-2] > arr[mid-1] and arr[mid-1] < arr[mid]: #found it!
        return mid-1;

    if arr[mid-1] > arr[mid-2]:
        return local_minima(arr, start, mid);
    else:
        return local_minima(arr, mid, end);

Обратите внимание, что я просто возвращаю индекс n. Чтобы распечатать тройку, просто возвращаем -1 и +1 в возвращаемый индекс. источник

Ответ 2

Похоже, что вы спрашиваете:

У вас есть последовательность чисел. Он начинает уменьшаться и продолжает уменьшаться до элемента n, затем он начинает увеличиваться до конца последовательности. Найдите n.

Это (неоптимальное) решение в линейном времени:

for (i = 1; i < length(A) - 1; i++)
{
    if ((A[i-1] >= A[i]) && (A[i] <= A[i+1]))
        return i;
}

Чтобы добиться лучшего, чем линейное время, вам нужно использовать информацию, полученную из того факта, что серия уменьшается, а затем увеличивается.

Рассмотрим разницу между A[i] и A[i+1]. Если A[i] > A[i+1], то n > i, так как значения все еще уменьшаются. Если A[i] <= A[i+1], то n <= i, так как значения теперь увеличиваются. В этом случае вам нужно проверить разницу между A[i-1] и A[i].

Это решение в лог-времени:

int boundUpper = length(A) - 1;
int boundLower = 1;
int i = (boundUpper + boundLower) / 2; //initial estimate

while (true)
{
    if (A[i] > A[i+1])
        boundLower = i + 1;
    else if (A[i-1] >= A[i])
        return i;
    else
        boundUpper = i;

    i = (boundLower + boundUpper) / 2;
}

Я оставлю это вам, чтобы добавить необходимую проверку ошибок в случае, если A не имеет элемента, удовлетворяющего критериям.

Ответ 3

Линейный вы могли бы просто выполнить путем итерации через набор, сравнивая их все.

Вы также можете проверить наклон первых двух, затем сделать своего рода двоичную отбивную/в порядке прохождения пары, пока не найдете один из противоположных наклонов. Думаю, что это будет амортизироваться дольше, чем n, хотя это не гарантируется.

edit: просто понял, что означает ваш заказ. Метод двоичной дробь гарантированно сделает это в <n времени, так как гарантированно будет точка изменения (предполагая, что ваш N-1, N-2 - последние два элемента списка). Это означает, что вам просто нужно найти его/один из них, и в этом случае двоичная отбивная сделает это в порядке log(n)