Znajdź triole w czasie lepszym niż liniowy tak, że A [n-1]> = A [n] <= A [n + 1]

Question

Sekwencja liczb została podana w wywiadzie takim, że A[0] >= A[1] i A[N-1] >= A[N-2]. Poproszono mnie, abym znalazł przynajmniej jedną trójkę, taką, że A[n-1] >= A[n] <= A[n+1].

Próbowałem rozwiązać w iteracjach. Interviewer spodziewał się lepszego niż liniowe rozwiązanie czasu. Jak powinienem podejść do tego pytania?

Przykład: 9 8 5 4 3 2 6 7

Odpowiedź: 3 2 6

Answer 1

Linear można po prostu zrobić przez iteracja planie, porównując je wszystkie.

Można również sprawdzić nachylenie pierwszych dwóch, a następnie wykonać rodzaj dwójkowego obcinania/w kolejności porównywania par, aż znajdzie się jedno z przeciwnych nachyleń. Oznaczałoby to, że amortyzuje się to lepiej niż n, chociaż nie jest to gwarantowane.

edytuj: właśnie zdałem sobie sprawę, co znaczyło twoje zamówienie. Metoda binarnego obcinania gwarantuje to w czasie <n, ponieważ gwarantowany jest punkt zmiany (zakładając, że twoje N-1, N-2 są ostatnimi dwoma elementami listy). Oznacza to po prostu trzeba go znaleźć/jeden z nich, w którym to przypadku kotlet binarne zrobi to w celu log(n)

Answer 2

Możemy rozwiązać ten problem w czasie korzystania O(logn) podzielić & przejęcie aka. wyszukiwanie binarne. Lepsze niż czas liniowy. Więc musimy znaleźć trójkę tak, że A[n-1] >= A[n] <= A[n+1].

Najpierw znajdź środek danej tablicy. Jeśli połowa jest mniejsza od lewej i większa od prawej. następnie wróć, to twoja odpowiedź. Nawiasem mówiąc, byłaby to baza w rekursji. Także jeśli len(arr) < 3 to też wróć. inna podstawa.

Teraz przychodzi scenariusz rekursji. Kiedy powracać, będziemy musieli dokonać dokładnej inspekcji. W tym przypadku, jeśli mid jest większy niż element po lewej stronie, rozważ początek od lewej tablicy jako podproblem i recurse z tą nową tablicą. tj. w warunkach namacalnych w tym momencie, mielibyśmy ...2 z indeksem n będącym 6. Więc przesuwamy się w lewo, aby zobaczyć, czy element po lewej stronie 2 kończy triplet.

W przeciwnym razie, jeśli środek jest większy niż element na prawej pod-planszy, należy rozważyć środek + 1 na prawo macierzy jako subproblem i rekurencję.

---

Więcej Teoria: Powyższy powinny być wystarczające, aby zrozumieć problem, ale czytaj dalej. Problem zasadniczo sprowadza się do znalezienia lokalnych minimów w danym zestawie elementów. Liczba w tablicy nazywana jest lokalnymi minima, jeśli jest mniejsza niż jej lewy i prawy numer, który precyzyjnie sprowadza się do A[n-1] >= A[n] <= A[n+1].

Dana tablica tak, że jej pierwsze 2 elementy zmniejszają się, a ostatnie 2 elementy mają coraz więcej MAJĄ minimalne lokalne. Dlaczego? Pozwala to udowodnić to przez negację. Jeśli pierwsze dwie liczby maleją, a nie ma lokalnych minimów, oznacza to, że trzecia liczba jest mniejsza od drugiej liczby. w przeciwnym razie druga liczba byłaby lokalnymi minimami. Zgodnie z tą samą logiką czwarta liczba będzie musiała być mniejsza niż trzecia i tak dalej. Więc liczby w tablicy będą musiały być malejące.Co narusza ograniczenie dwóch ostatnich liczb będących w porządku rosnącym. Dowodzi to przez zaprzeczenie, że muszą istnieć lokalne minimalne wartości.

Powyższa teoria sugeruje podejście liniowe O(n), ale zdecydowanie możemy zrobić lepiej. Ale teoria zdecydowanie daje nam inną perspektywę dotyczącą problemu.

---

Kod: Oto kod python (FYI - został wpisany w stackoverflow edytora tekstu odręczne, może 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); 

Pamiętaj, że właśnie zwróciłem indeks n. Aby wydrukować potrójny, po prostu wykonaj -1 i +1 do zwróconego indeksu. source

Answer 3

Brzmi jak co pytasz to:

Masz sekwencję liczb. Zaczyna zmniejszać i nadal maleje aż do elementu n, następnie zaczyna zwiększać się aż do końca sekwencji. Znajdź n.

To (nieoptymalne) rozwiązanie w czasie liniowym:

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

Aby to zrobić lepiej niż czasu linearnego, trzeba korzystać z informacji, które można uzyskać z faktu, że seria maleje wtedy wzrasta.

Rozważ różnicę między A[i] i A[i+1]. Jeśli A[i] > A[i+1], to n > i, ponieważ wartości nadal maleją. Jeśli A[i] <= A[i+1], a następnie n <= i, ponieważ wartości są teraz zwiększenie. W takim przypadku musisz sprawdzić różnicę między A[i-1] i A[i].

Jest to rozwiązanie w czasie dziennika:

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; 
} 

Zostawię to do ciebie, aby dodać niezbędną kontrolę błędów w przypadku, A nie posiada elementu spełniającego kryteria.