Recenze

Jak začít zpátečku?

Dané pole arr[] , úkolem je zvrátit pole. Obrácení pole znamená přeskupení prvky takové, že První prvek se stává poslední se druhý prvek se stává předposlední a tak dále.

Příklady:

Vstup: arr[] =
Výstup:
Vysvětlení: První prvek 1 přesune na poslední pozici, druhý prvek 4 přesune do předposledního a tak dále.

Vstup: arr[] =
Výstup:
Vysvětlení: První prvek 4 přesune na poslední pozici, druhý prvek 5 přesune na předposlední a tak dále.

[Naivní přístup] Použití dočasného pole – O(n) čas a O(n) prostor
[Očekávaný přístup – 1] Použití dvou ukazatelů – O(n) Čas a O(1) Prostor
[Očekávaný přístup – 2] Záměnou prvků – O(n) Čas a O(1) Prostor
[Alternativní přístup] Použití rekurze – O(n) čas a O(n) prostor
Použití vestavěných metod – O(n) čas a O(1) prostor

[Naivní přístup] Použití dočasného pole – O(n) čas a O(n) prostor

Vytvořit dočasný pole stejné velikosti jako původní pole.
Nyní zkopírujte všechny prvky z původního pole do dočasného pole obrácené pořadí .
Nakonec zkopírujte všechny prvky z dočasného pole zpět do původního pole.

Pracovní:

Níže je implementace algoritmu:

      Jáva

      PYTHON

      JavaScript

Výstup

5 6 2 3 4 1

Časová složitost: O(n), Kopírování prvků do nového pole je lineární operace.
Pomocný prostor: O(n), protože k uložení obráceného pole používáme další pole.

[Očekávaný přístup – 1] Použití dvou ukazatelů – O(n) Čas a O(1) Prostor

Cílem je zachovat dva ukazatele: vlevo si přesně , takové, že vlevo body na začátek pole a přesně ukazuje na konec pole.

Zatímco levý ukazatel je menší než pravý ukazatel, prohoďte prvky na těchto dvou pozicích. Po každé výměně, přírůstek ο vlevo ukazatel a dekrementovat ο přesně ukazatel se posune směrem ke středu pole. Tím dojde k záměně všech prvků v první polovině s odpovídajícími prvky ve druhé polovině.