Není rychlý.
Minimalne toto se da rici i o Jave, ktera je po svete dost rozlezla.
Těžko říct, jestli je pomalejší Java nebo Python zkompilovaný do nativního kódu. V každém případě jsou z principu pomalé fintovní řešení v Pythonu v tomto vláknu diskuze, protože mají kvadratickou větší složitost. Mě se zde líbilo pouze řešení je v Javě od Kolemjdoucího, které je čitelné a zároveň má lineární složitost. Podobně by to šlo Pythonu, kdyby se chtělo.
Kvadratickou v čem?
Kvadratickou vzhledem k počtu prvků v matici a záleží na implementaci toho otáčení matice zda půjde o zátěž CPU nebo alokaci paměti nebo obojí. Nechtěl jsem si svůj algoritmus chválit, když na první pohled vypadá komplikovaněji, ale je fakt že má optimální složitost protože nealokuje zbytečnou paměť a pouze jednou projde potřebná data. Implementační detail je že jsem to kvůli čitelnosti udělal v dvourozměrném poli, což Java implementuje jako pole polí a to je méně efektivní než jedno velké pole.
Všichni ti co kvůli přečtení jedné strany matice tu celou matici otáčejí (což může sice být jedno volání knihovny, ale není to levné) mi připadají jako že úplně ignorují efektivitu, jen aby výsledný kód vypadal na první pohled zajímavěji. Pokud by tento příklad byl součástí přijímacího pohovoru tak předpokládám že by hned další krok by byla diskuse o efektivitě různých řešení, a ta by mi o kandidátovi řekla pravděpodobně víc než konkrétní navržené řešení.
Mimochodem, měl jsem tam chybu která se někdy projevovala při lichých počtech řádků nebo sloupců (speciální případ je 1xN nebo Nx1 jak tu někdo psal), správně je to takhle:
public class Snake {
public static int[] solve(int[][] input) {
int height = input.length;
int width = height == 0 ? 0 : input[0].length;
int[] result = new int[width * height];
for (int i = 0, res = 0; res != result.length; i++) {
for (int j = i; j < width - i; j++) {
result[res++] = input[i][j];
}
for (int j = i + 1; j < height - i; j++) {
result[res++] = input[j][width - 1 - i];
}
if (res == result.length) {
// odd number of rows or columns
break;
}
for (int j = width - 2 - i; j >= i; j--) {
result[res++] = input[height - 1 - i][j];
}
for (int j = height - 2 - i; j > i; j--) {
result[res++] = input[j][i];
}
}
return result;
}
public static void main(String[] args) {
int[][] input = new int[][] {
{1,3,5,7,6},
{2,5,8,2,5},
{9,2,4,6,2},
{5,7,8,1,2},
{4,2,3,5,6},
{8,6,5,4,2}
};
int[] result = solve(input);
for (int i : result) {
System.out.println(i);
}
}
}
137 Odpovědí
22507 Zhlédnutí