Qual è il numero minimo di swap adiacenti necessari per separare un elenco di 0 e 1?
Sto cercando di risolvere un problema di strutture dati e algoritmi, che afferma che dato un gruppo di 1 e 0, raggruppa le cifre in modo tale che tutti gli 0 siano insieme e tutti gli 1 siano insieme. Qual è il numero minimo di scambi necessari per ottenere ciò se si possono scambiare solo due elementi adiacenti? Non importa quale gruppo sia a quale fine.
Per esempio:
[0,1,0,1] = [0,0,1,1] 1 swap
[1,1,1,1,0,1,0] = [1,1,1,1,1,0,0] 1 swap
[1, 0, 1, 0, 0, 0, 0, 1] = = [1,1,1,0,0,0,0,0] 6 scambi
Nota che questo è diverso dalle domande poste qui:
Trova il numero minimo di swap richiesti in modo che tutti gli 0 e tutti gli 1 siano insieme
Non sto ordinando l'array, sto solo cercando di raggruppare tutti gli 0 e tutti gli 1 insieme e non importa quale sia a quale fine.
Non ho davvero la minima idea da dove cominciare. Qualcuno può aiutarmi?
Risposte
Concentriamoci sugli zeri. Ogni scambio sposta un singolo zero di una singola posizione più vicino all'ordine finale. Quindi possiamo trovare il numero di scambi trovando il numero di zeri spostati e la gravità dello spostamento.
Partiamo dal presupposto che gli zeri finiscano all'inizio dell'array. Terremo traccia di due cose: count_of_ones e displacement, entrambi inizializzati a zero. Ogni volta che troviamo un 1, incrementiamo count_of_ones. Ogni volta che troviamo uno 0, aumentiamo lo spostamento di count_of_ones.
Quindi lo facciamo nella direzione opposta. Entrambi i modi sono lineari, quindi questo è lineare.
Ad esempio 1010001
1: count_of_ones: 0 -> 1
0: displacement: 0 -> 1
1: count_of_ones: 1 -> 2
0: displacement: 1 -> 3
0: displacement: 3 -> 5
0: displacement: 5 -> 7
1: count_of_ones: 2 -> 3
La risposta per questa direzione è lo spostamento finale, o 7. Andando dall'altra parte otteniamo 5. La risposta finale è 5.
In effetti, la somma degli spostamenti finali (iniziando vs finendo con tutti zeri) sarà sempre uguale a num_zeroes * num_ones. Questo dimezza il lavoro (sebbene sia ancora lineare).
Dai commenti sembra che alcune persone non abbiano capito la mia risposta. Ecco un'implementazione di Ruby per rendere le cose più chiare.
def find_min_swaps(arr)
count_of_ones = 0
displacement = 0
arr.each do |v|
count_of_ones += 1 if v == 1
displacement += count_of_ones if v == 0
end
count_of_zeroes = arr.length - count_of_ones
reverse_displacement = count_of_ones * count_of_zeroes - displacement
return [displacement, reverse_displacement].min
end
Gli zeri finiscono a sinistra se displacement <reverse_displacement, o se sono uguali, oppure a destra se displacement> reverse_displacement.
Sia SUM0
la somma degli indici (a base 0) di tutti gli zeri, e SUM1
sia la somma degli indici di tutti gli uno. Ogni volta che si scambia 10
-> 01
, SUM0
scende di uno e SUM1
sale di uno. Vanno dall'altra parte quando scambi 01
-> 10
.
Diciamo che hai N0
zeri e N1
uno. Se gli zeri fossero stati impacchettati insieme all'inizio dell'array, allora avresti SUM0 = N0*(N0-1)/2
. È il più piccolo SUM0
che puoi avere.
Poiché un singolo scambio adiacente può ridursi SUM0
esattamente di uno, sono necessari SUM0 - N0*(N0-1)/2
scambi esattamente per raggruppare gli zeri nella parte anteriore. Allo stesso modo, sono necessari degli SUM1 - N1*(N1-1)/2
scambi per mettere insieme quelli nella parte anteriore.
La tua risposta è il più piccolo di questi numeri: min( SUM0 - N0*(N0-1)/2 , SUM1 - N1*(N1-1)/2 )
Questi valori sono tutti facili da calcolare in tempo lineare.
Un approccio semplice utilizzando Bubble Sort, che accetta O (n 2 ), sarebbe questo:
public class MainClass {
public static void main(String[] args) {
int[] arr = new int[]{1, 0, 0, 0, 0, 0, 0, 1, 0};
int minSwaps = minimumSwaps(arr);
System.out.println("Minimum swaps required: " + minSwaps);
}
public static int minimumSwaps(int[] array) {
int[] arr1 = array.clone(), arr2 = array.clone();
int swapsForRight = 0, swapsForLeft = 0;
boolean sorted = false;
while (!sorted) {
sorted = true;
for (int i = 0; i < arr1.length - 1; i++) {
if (arr1[i + 1] < arr1[i]) {
int temp = arr1[i + 1];
arr1[i + 1] = arr1[i];
arr1[i] = temp;
sorted = false;
swapsForRight++;
}
}
}
sorted = false;
while (!sorted) {
sorted = true;
for (int i = 0; i > arr2.length - 1; i++) {
if (arr2[i + 1] < arr2[i]) {
int temp = arr2[i + 1];
arr2[i + 1] = arr2[i];
arr2[i] = temp;
sorted = false;
swapsForLeft++;
}
}
}
return swapsForLeft > swapsForRight ? swapsForRight : swapsForLeft;
}
}