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

Question

В интервью было дано последовательное число таких цифр, что A[0] >= A[1] и A[N-1] >= A[N-2]. Меня попросили найти по меньшей мере один триплет, такой как A[n-1] >= A[n] <= A[n+1].

Я попытался решить в итерациях. Интервьюер ожидал большего, чем линейное решение. Как мне подойти к этому вопросу?

Пример: 9 8 5 4 3 2 7 6

Ответ: 3 2 6

Answer 1

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

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

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

Answer 2

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

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

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

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

---

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

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

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

---

Код: Вот питона код (FYI - был набран в текстовом редакторе StackOverflow Freehand, это может misbheave).

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 в возвращаемый индекс. source

Answer 3

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

У вас есть последовательность чисел. Он начинает уменьшаться и продолжает уменьшаться до элемента 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 не имеет элемента, удовлетворяющий критериям.