[NotABigFan]

Wczorajszy #dailycodingproblem pozostał nietknięty. Dzisiaj wrzucę coś stricte od siebie co mogłoby się pojawić gdzieś na interview w formie rozgrzewki.

Napisz funkcję przesuwającą cyklicznie tablicę xs w prawo o k pozycji. Funkcja ma działać w miejscu (pamięć O(1)) i czasie O(n).

np. xs=[1, 2, 3, 4, 5], k=2 -> [4, 5, 1, 2, 3]
Jeżeli ktoś jeszcze nie wie czym jest przesunięcie cykliczne wyjaśniam to formalnie w poprzednim wpisie. Zachęcam jeszcze spróbować rozwiązać poprzednie zadanie bo jest niebanalne.

#dailycodingproblem #programowanie

[ptasigryp]

@NotABigFan: Ja właśnie robie wczorajsze, zaraz wrzuce bo kiedyś już je rozwiązywałem ale zgubiłem kod ( ͡° ͜ʖ ͡°)

[mk321]

@NotABigFan:

1. Najprostsze rozwiązanie tzn. brać ostatni element i zamienić z pierwszym (swap). A potem przesunąć wszystkie pozostałe.
-> Pewnie złożoność tego to O(n*n)?

2. To zamiast przesuwać, po prostu wyliczyć miejsce gdzie będzie po wszystkich

[NotABigFan]

-> Pewnie złożoność tego to O(n*n)?

@mk321: O(k*n)

Samo przechowywanie tablicy w pamięci chyba zajmuje już O(n) (bo jest elementów)?

Tu chodzi o dodatkową pamięć, to co dostaje funkcja w formie argumentów nie

[passage]

@NotABigFan: a elementy są tak jak w przykładzie? W sensie posortowane i różnica między nimi jest zawsze taka sama? ( ͡° ͜ʖ ͡°)

[NotABigFan]

@passage: assume nothing, trust no one ( ͡° ͜ʖ ͡°)

[asunez]

@passage: assume nothing, trust no one ( ͡° ͜ʖ ͡°)

@NotABigFan: tak mi się skojarzyło, sorry za zaśmiecenie wpisu ;)

[S.....s]

@NotABigFan jeśli k mod len(xs) = 0 to nic, jeśli nie to dla każdego elementu z indeksem od do k mod len(xs) swapujemy z kolejnym o indeksie +k aż trafimy na początkowy (pierwszy zapisujemy do tempa żeby nie zniknął) (oczywiscie ten indeks +k modulo no może być większy niż len*(xs)

[NotABigFan]

@SuppressWarnings: średnio kumam, może jakiś pseudokod? ( ͡° ͜ʖ ͡°)

[ptasigryp]

@NotABigFan: mam rozwiązanie z O(2n) czyli w sumie O(n). Zaraz napisze działający kod i sprawdze czy napewno smiga ok.

[S.....s]

@NotABigFan jak mi się uda na telefonie to zaraz będzie, jak nie to wieczorem xd

[ptasigryp]

@NotABigFan: @SuppressWarnings: https://pastebin.com/feRWPQZi

[NotABigFan]

@ptasigryp: jak ktoś nie ogarnia co swift robi to leci to tak:
wykonujemy 3 reversy w miejscu:
jeden dla indeksów od 0 do n-k-1
drugi dla indeksów od n-k do n-1
trzeci dla całej

[LewitujacyMnich]

@NotABigFan: Najlepsze na co udało mi się wpaść ( ͡° ʖ̯ ͡°)
https://pastebin.com/qfc4qnDT

Jakby lista miała zawsze nieparzystą ilość elementów to by obeszło się bez trzymania dodatkowego indexu.