NOVINKA! E-learningové kurzy umělé inteligence. Nyní AI za nejlepší ceny. Zjisti více:
NOVINKA – Víkendový online kurz Software tester, který tě posune dál. Zjisti, jak na to!

Diskuze: Algoritmy - Nejefektivnější řešení

V předchozím kvízu, Online test znalostí PHP, jsme si ověřili nabyté zkušenosti z kurzu.

Aktivity
Avatar
pluto-ppes
Člen
Avatar
pluto-ppes:21.1.2016 14:13

Ahoj,
rád bych se poradil a prodiskutoval s ostatními jaká by byla nejefektivnější cesta k řešení následujícího zadání níže. Přikládám i vlastní řešení, ať je nad čím diskutovat ;-) Bylo to zadání do jedné soutěže, tak ho možná taky někdo řešil, bohužel se neuvádělo výtězné řešení, ani hodnocení odeslaného kódu.

Vlasní řešení:

function solution($A) {
    // write your code in PHP5.5
    $places = array_unique($A);
    $values = array_unique($A);
    $last_position = array();
    for($i = 0;$i < count($A);$i++){
        $key = array_keys($values,$A[$i]);
        $last_position[$key[0]] = $i;
        if(!empty($places)){
            unset($places[$key[0]]);

            if(empty($places)){
                return max($last_position) - min($last_position)+1;
            }
        }
    }

}
 
Editováno 15.1.2021 19:53
 
Odpovědět
21.1.2016 14:13
Avatar
coells
Tvůrce
Avatar
Odpovídá na pluto-ppes
coells:22.1.2016 10:30

Máš tam tři problémy:

  1. když ke vstupnímu poli z příkladu připojím 7, měl bys vrátit 4, ale vracíš 5, takže řešení není správně
  2. array_unique nesplňuje zadání O(N), protože třídí, tyhle funkce nesmíš používat
  3. PHP není dobré na algoritmické úlohy, funkce jako array_unique a array_keys schovávají reálnou složitost algoritmu
 
Nahoru Odpovědět
22.1.2016 10:30
Avatar
pluto-ppes
Člen
Avatar
Odpovídá na coells
pluto-ppes:25.1.2016 21:32

Díky za odpověď. Hned jsem zase o něco chytřejší :-)

 
Nahoru Odpovědět
25.1.2016 21:32
Avatar
Ondrca
Tvůrce
Avatar
Odpovídá na pluto-ppes
Ondrca:25.1.2016 22:02

To je to zadání z Alza developer challenge, že jo? :D

Nahoru Odpovědět
25.1.2016 22:02
Zase jsem o něco chytřejší
Avatar
Drahomír Hanák
Tvůrce
Avatar
Odpovídá na pluto-ppes
Drahomír Hanák:25.1.2016 22:59

Pro řešení v lineárním čase jde třeba využít fakt, že hodnoty jsou celá čísla od 0 do N - 1 takže můžeš mít pomocné pole indexované těmi hodnotami. S tím pak můžeš zjistit počet výskytů jednotlivých hodnot v dané sekvenci v konstantním čase, takže by mělo stačit projít jednou to pole a posouvat ukazatel na začátek uvažované sekvence, dokud se hodnota na začátku v sekvenci opakuje. Zkus to ale ověřit (buď najdi protipříklad, nebo dokaž, že tak skutečně narazíš na nejkratší sekvenci, která obsahuje všechny hodnoty alespoň jednou)

 
Nahoru Odpovědět
25.1.2016 22:59
Avatar
pluto-ppes
Člen
Avatar
Odpovídá na Ondrca
pluto-ppes:26.1.2016 7:55

Jo přesně alza challenge, je to už delší doba od soutěže tak jsem si dovolil to zveřejnit, aby jsme si tu mohli podiskutovat.

 
Nahoru Odpovědět
26.1.2016 7:55
Děláme co je v našich silách, aby byly zdejší diskuze co nejkvalitnější. Proto do nich také mohou přispívat pouze registrovaní členové. Pro zapojení do diskuze se přihlas. Pokud ještě nemáš účet, zaregistruj se, je to zdarma.

Zobrazeno 6 zpráv z 6.