ado21 píše:
Kód:
/*
* k je pocet maximalnych prvkov
*/
public int[] najdiMax(int[] pole, int k)
{
int[] vysledok = new int[k];
for(int i = 0; i < vysledok.length; i++) {
int max = Integer.MIN_VALUE;
int indexMax = 0;
for (int m = 0; m < pole.length; m++) {
if (pole[m] > max) {
max = pole[m];
indexMax = m;
}
}
vysledok[i] = max;
pole[indexMax] = Integer.MIN_VALUE;
}
return vysledok;
}
Tvoje ma
vzdy 0(nlogn). Oznacme pocet maximalnych prvokov k. Moje riesenie ma 0(nk) a v pripade
k << n, co je asi velmi realne predpokladat, bude mat
O(kn) = O(n). V jeho pripade sa je k = 3...
vyznam slova "jednoduchost" si predstavujem tak, ze riesenie bude vyzadovat menej zdrojoveho kodu
Kód:
public static int[] najdiMax(int[] pole, int k)
{
int[] vysledok = new int[k];
Arrays.sort(pole);
System.arraycopy(pole, pole.length-k, vysledok, 0, k);
return vysledok;
}
a z pohladu rychlosti tam nieje takmer ziadny rozdiel
Kód:
public static void main(String[] args) {
int[] vstup = {9,2,3,4,1,6,7,8,4};
long start = System.currentTimeMillis();
for (int i =0;i<10000000; i++) {
int[] vystup = najdiMax(vstup, 3);
}
System.out.println("done "+(System.currentTimeMillis()-start));
start = System.currentTimeMillis();
for (int i =0;i<10000000; i++) {
int[] vystup = najdiMax2(vstup, 3);
}
System.out.println("done "+(System.currentTimeMillis()-start));
}
public static int[] najdiMax(int[] pole, int k)
{
int[] vysledok = new int[k];
for(int i = 0; i < vysledok.length; i++) {
int max = Integer.MIN_VALUE;
int indexMax = 0;
for (int m = 0; m < pole.length; m++) {
if (pole[m] > max) {
max = pole[m];
indexMax = m;
}
}
vysledok[i] = max;
pole[indexMax] = Integer.MIN_VALUE;
}
return vysledok;
}
public static int[] najdiMax2(int[] pole, int k)
{
int[] vysledok = new int[k];
Arrays.sort(pole);
System.arraycopy(pole, pole.length-k, vysledok, 0, k);
return vysledok;
}
