La mia uscita è [1, 2, 2, 4, 3], non corretta. Dovrebbe essere [1, 2, 2, 3, 4]. Ma non riesco a trovare l'errore nel mio codice. Qualcuno potrebbe aiutarmi a scoprire l'errore dell'algoritmo? Grazie. Il mio intero codice viene copiato di seguito. Può essere implementato.
Domanda:
Data una matrice di n oggetti con k colori diversi (numerati da 1 a k), ordinali in modo che gli oggetti dello stesso colore siano adiacenti, con i colori nell'ordine 1, 2, ... k.
Esempio: Dato colors = [3, 2, 2, 1, 4], k = 4, il codice dovrebbe ordinare i colori sul posto in [1, 2, 2, 3, 4].
Requisiti: Una soluzione piuttosto semplice è un algoritmo a due passaggi che utilizza l'ordinamento conteggio. Ciò costerà O (k) memoria aggiuntiva. Puoi farlo senza usare memoria aggiuntiva?
import java.util.Arrays;
public class SortColorsII {
public static void sortColors2(int[] colors, int k) {
int count = 0;
int start = 0;
int end = colors.length-1;
while (count <= k) {
int min = Integer.MAX_VALUE;
int max = Integer.MIN_VALUE;
for (int i = start; i < end; i++) {
min = Math.min(min, colors[i]);
max = Math.max(max, colors[i]);
}
int left = start;
int right = end;
int cur = left;
while(cur <= right) {
if (colors[cur] == min) {
swap(left, cur, colors);
cur++;
left++;
} else if(colors[cur] == max) {
swap(cur, right, colors);
right--;
} else {
cur++;
}
}
count += 2;
start = left;
end = right;
}
}
private static void swap(int left, int right, int[] colors) {
int tmp = colors[left];
colors[left] = colors[right];
colors[right] = tmp;
}
public static void main(String[] args){
int[] colors = new int[]{3, 2, 2, 1, 4};
int k = 4;
sortColors2(colors, k);
String res = Arrays.toString(colors);
System.out.println(res);
}
}
risposte:
1 per risposta № 1La ricerca minima / massima esclude l'ultimo elemento. Usa un limite superiore inclusivo:
for (int i = start; i <= end; i++)