Sto cercando di trovare un algoritmo efficiente per il seguente algoritmo.
Ho una sequenza composta da liste di indici che indicano gli indici da rimuovere. La semantica è tale che ogni sequenza deve essere eseguita in ordine. Voglio prendere queste sequenze e appiattirle in una sequenza di indici assoluti da rimuovere.
Questo può essere ottenuto eseguendo una serie di setacci (in qualche modo simili al Setaccio di Eratostene). L'avvertenza è che questa tecnica è lenta (quadratica).
Quindi questo gruppo di indici relativi:
R0: 0 3 10 15
R1: 2 7 20
R2: 1 11 12 14 17
R3: 0 1 2
Corrisponderebbe a questo gruppo di indici assoluti:
A0: 0 3 10 15
A1: 4 9 22
A2: 2 17 18 20 24
A3: 1 5 6
E quando si sono fusi in una sequenza di indici assoluti, avrei il seguente:
A': 0 1 2 3 4 5 6 9 10 15 17 18 20 22 24
Potrebbe esserci un numero qualsiasi di sequenze relative, ognuna delle quali può contenere un numero qualsiasi di elementi e può presentare ampi intervalli tra gli indici. Le sequenze relative all'inserimento sono ordinate in ordine crescente, ognuna delle quali potrebbe non contenere duplicati.
Non è necessario ottenere gli elenchi intermedi A# . Mi interessa solo la lista A' dagli input R# .
Chiarificazione dell'algoritmo
Prendiamo l'elenco degli interi non negativi
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 ...
E rimuovi gli indici dati da R0
Quindi abbiamo
1 2 4 5 6 7 8 9 10 11 12 13 14 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 ...
I valori rimossi producono A0 ( 0 3 10 15 )
Ora rimuovi gli indici dati da R1
1 2 5 6 7 8 10 11 12 13 14 16 17 18 19 20 21 23 24 25 26 27 28 29 30 ...
I valori rimossi producono A1 ( 4 9 22 )
Ora rimuovi gli indici dati da R2
1 5 6 7 8 10 11 12 13 14 16 19 21 23 25 26 27 28 29 30 ...
I valori rimossi generano A2 ( 2 17 18 20 24 )
Ora rimuovi gli indici dati da R3
7 8 10 11 12 13 14 16 19 21 23 25 26 27 28 29 30 ...
I valori rimossi producono A3 ( 1 5 6 )