Badanie sekwencji rosnącej - Java

pytanie zadane 28 marca 2019 w Java przez pionas0407 Gaduła (4,620 p.)

Hej!

W ostatnim czasie szlifuje swoje umiejętności wraz ze stroną CodeSignal.

Po wykonaniu kilku pierwszych zadań bez większych problemów natrafiłem na zadanie które sprawia mi zakłopotanie.

Treść zadania:

Zrobić funkcję która jako argument dostaje tablicę INT i sprawdza czy istnieje tam sekwencja rosną tzn. a0 < a1 < a2 < ... < an, można usunąć jeden element z tablicy.

Czyli sekwencja

{1, 2, 4, 3} jest sekwencją bo można usunąć 4.

{1, 2, 4, 4, 5, 4} nie jest, ponieważ mimo usunięcia jednego elementu nie uzyskamy sekwencji.

Rozwiązałem to zadania już na dwa sposoby, pierwszy -> błędny który przeszedł tylko 16 testów na 19.

Drugi sposób (aktualny, lepszego nie wymyśliłem) rozwiązuje 34 na 38 testów. Wymyśliłem bardzo słaby algorytm(pod względem optymalizacji).

Algorytm:

Sprawdza czy tablica (bez usunięcia elementów) jest sekwencją - > jeżeli tak to koniec zadania -> jeżeli nie -> kopiuje tablice do tablicy pomocniczej -> usuwa 0 element - > cofa się do pkt 1. -> jeżeli nie -> usuwa 1 element... -> cofa się do pkt 1. -> jeżeli nie usuwa n-ty element -> ...

Algorytm działa, jednak max czasu na wykonanie pracy programu to 3 sekundy. Na 35 przykładzie wywala się bo tablica jest za duża a ten program jest tak słabo wydajny, że więcej czasu by mu to zajęło.

Ktoś ma jakiś pomysł na wydajniejszy algorytm :D?

komentarz 28 marca 2019 przez marcin99b Szeryf (82,180 p.)

Nie wiem czemu, ale czytając to mam wrażenie, że to reklama strony

CodeSignal

komentarz 28 marca 2019 przez pionas0407 Gaduła (4,620 p.)

Nie reklamuję tej strony ;) mogę nawet usunąć nazwę tej strony, po prost trapi mnie to pytanie ;)

1 odpowiedź

odpowiedź 28 marca 2019 przez marcin99b Szeryf (82,180 p.)
wybrane 28 marca 2019 przez pionas0407

Najlepsza

ja bym zrobił to tak, że

przelatuje przez wszystkie elementy tablicy, a podczas tego
zapisuje referencje do ostatniego elementu tablicy
porównuje z obecnym i sprawdzam czy flaga isChanged == false (domyślnie false)
jeśli się nie zgadza, usuwam obecny i zmieniam flage isChanged na true

jeśli jest ustawiona na true, a muszę zmienić
wyrzucam info że coś tu się nie zgadza
mogę podać przy tym info który element nie pasuje

Specjalistą od hardkorowej optymalizacji nie jestem, to bardziej tak na logikę co najprościej napisać i co sprawia wrażenie prawidłowego

komentarz 28 marca 2019 przez pionas0407 Gaduła (4,620 p.)

Okej... do końce nie rozumiem Twojej koncepcji ale spróbuje to zaimplementować jutro i przetestować rezultaty ;)! Możesz troszkę to bardziej opisać?

komentarz 28 marca 2019 przez marcin99b Szeryf (82,180 p.)

a czego dokładnie nie rozumiesz?

coś na zasadzie

int lastElement;
var isChanged = false
foreach(var element in elements)
{
    if(element <= lastElement)
    {
        if(isChanged)
        {
            throw new Exception();
        }
        elements.Remove(element)
        isChanged = true;
    }
    lastElement = element;
}

//jak coś to bardziej pseudokod, niż coś co sobie skopiujesz i zadziała 
//chociaż... może i by zadziałało

komentarz 28 marca 2019 przez pionas0407 Gaduła (4,620 p.)

Dobra już rozumiem ;) Okej przetestuję Twoje rozwiązanie i dam znać czy poszło :D

komentarz 28 marca 2019 przez marcin99b Szeryf (82,180 p.)

W sensie wiesz

Pewnie eksperci od hardkorowej optymalizacji co do ułamków milisekundy by to skrytykowali
Ale kierując się zasadami zdrowego rozsądku i znośnej czytelności kodu, to rozwiązanie jest dość optymalne
Bo z jednej strony czytelność nie odstrasza, a z drugiej nie robi dużo zbędnych akcji
Ewentualnie z tymi ifami bym pokombinował, ale to już dodatek dla lepszej czytelności