Esimerkiksi kun $n=4$, listan $[3,1,4,2]$ voi järjestää seuraavasti:
$[3,1,4,2] \rightarrow [4,2,3,1] \rightarrow [1,2,3,4]$
Tässä tapauksessa ensimmäisessä operaatiossa $i=2$ ja toisessa operaatiossa $i=1$. Sen sijaan listaa $[3,1,2,4]$ ei ole mahdollista järjestää mitenkään operaation avulla.
Voit olettaa, että $n$ on välillä $2 \dots 10^5$. Tavoitteena on, että algoritmin aikavaativuus on $O(n)$ tai $O(n \log n)$.
Python
Toteuta tiedostoon
movesort.py
funktio check
, joka tarkastaa, voiko listan järjestää.def check(t): # TODO if __name__ == "__main__": print(check([3,1,4,2])) # True print(check([3,1,2,4])) # False print(check([1,2])) # True print(check([4,5,6,1,2,3])) # True print(check([4,5,6,3,2,1])) # FalseJava
Toteuta tiedostoon
MoveSort.java
metodi check
, joka tarkastaa, voiko listan järjestää.public class MoveSort { public boolean check(int[] t) { // TODO } public static void main(String[] args) { MoveSort m = new MoveSort(); System.out.println(m.check(new int[] {3,1,4,2})); // true System.out.println(m.check(new int[] {3,1,2,4})); // false System.out.println(m.check(new int[] {1,2})); // true System.out.println(m.check(new int[] {4,5,6,1,2,3})); // true System.out.println(m.check(new int[] {4,5,6,3,2,1})); // false } }