Algorytm MIN=MAX

0

Już 2 tydzień siedzę nad tym zadaniem, ale nie mogę wszystkiego ogarnąć. Treść zagadnienia:
"Proszę napisać funkcję, która dla tablicy jednowymiarowej o rozmiarze n, wyznacza
punkt podziału tej tablice na dwie podtablice spełniające własność: minimalna
wartość lewej podtablicy ( od indeksu 0 do indeksu k ) jest równa maksymalnej
wartości prawej podtablicy( tej od indeksu k+1 do n-1). Jeśli istnieje taki podział,
funkcja zwraca punkt podziału (indeks k). W przeciwnym przypadku zwraca
wartość –1.
0 1 2 3 4 5 6 7
Np. dla tablicy A={5, 4, 6 7, | 3,-4, 4,0 } takim punktem podziału jest indeks k=3.
Wartość minimalna lewej podtablicy od indeksu 0 do 3 wynosi 4. Maksymalna
wartość w prawej podtablicy od indeksu 4 do 7 wynosi również 4."

Proszę o pomocy. Wiem że trzeba(można) podzielić tablice na dwie podtablicy, i szukać min, max. A na koniec porównać ci 2 liczby, ale nie wiem jak to dokładniej napisać w kodzie?

1

Posortuj, poszukaj pierwszych dwóch powtarzających się elementów. Jak takie są, to pierwsza tablica jest od początku do pierwszego powtórzonego, a druga od drugiego powtórzonego do końca.

0
kq napisał(a):

Posortuj, poszukaj pierwszych dwóch powtarzających się elementów. Jak takie są, to pierwsza tablica jest od początku do pierwszego powtórzonego, a druga od drugiego powtórzonego do końca.

Dzieńki.

0
kq napisał(a):

Posortuj, poszukaj pierwszych dwóch powtarzających się elementów. Jak takie są, to pierwsza tablica jest od początku do pierwszego powtórzonego, a druga od drugiego powtórzonego do końca.

No chyba nie bardzo zgadza się z warunkami zadania.
Według Twojego algorytmu dla danych (1, 3, 4, 9, 9, 3, 2, 6, 7), zakładając, że miałeś na myśli sortowanie rosnące, dostajesz
(1, 3) oraz (3, 2, 6, 7)
Po pierwsze Twój podział nie wyczerpuje całej tablicy na wejściu, po drugie min(pierwsza) < max(druga).

0

Dla każdego k wyliczasz minimum prefiksu tablicy o długości k i maksimum sufiksu tablicy o długości n - k. Potem tylko iterujesz po tablicy i szukasz indeksu k, dla którego minimum prefiksu jest równe maksimum sufiksu. Złożoność czasowa liniowa, pamięciowa liniowa.

0

A teraz jeżeli można, jak dla 1 rocznika studiów? Czuli jak dla dziecka)

0

       A={5, 4, 6, 7, | 3, -4, 4,  0 }
 minA={5, 4, 4, 4,   3, -4, -4, -4 }
maxA={7, 7, 7, 4,   4,  4,  0,  -inf }
Tniemy tam, gdzie wartości są równe.

1
Afish napisał(a):

Dla każdego k wyliczasz minimum prefiksu tablicy o długości k i maksimum sufiksu tablicy o długości n - k. Potem tylko iterujesz po tablicy i szukasz indeksu k, dla którego minimum prefiksu jest równe maksimum sufiksu. Złożoność czasowa liniowa, pamięciowa liniowa.

Czy przypadkiem złożoność czasowa nie będzie n^2? W każdej iteracji szukanie min i max jest liniowe, a musimy je zrobić dla każdego k.

2

Może być i n^10, ale jak zaimplementujesz poprawnie, to będzie liniowa.

0
Afish napisał(a):

Może być i n^10, ale jak zaimplementujesz poprawnie, to będzie liniowa.

Żeby to było liniowe, to każda iteracja Twojego opisu "Dla każdego k wyliczasz ..." (a k jest zależne bezpośrednio od n) musiałaby odbywać się w stałym, niezależnym od n czasie.
Podaj przykład tej "poprawnej implementacji".

1 użytkowników online, w tym zalogowanych: 0, gości: 1, botów: 0