Esiste un algoritmo che, dato un array ordinato, scambia tutti gli primi elementi unici all'inizio della matrice e i duplicati fino alla fine, pur rimanendo stabile per entrambi il subarray univoco e il sottoarray duplicato e che viene eseguito in O(n) swaps (e preferibilmente in un passaggio)? Dovrebbe restituire la lunghezza della parte univoca dell'array.
Input / risultato di esempio contrato (usando python perché è facile da leggere):
>>> A = [1, 1, 2, 2, 3, 3, 4, 4, 5, 5] # already sorted
>>> r = Unique(A)
>>> r
5
>>> A
[1, 2, 3, 4, 5, 1, 2, 3, 4, 5]
>>> A[:r] # the sorted portion
[1, 2, 3, 4, 5]
>>> A[r:] # the duplicates portion
[1, 2, 3, 4, 5]
Stabilità significa che anche se due o più chiavi sono uguali, l'ordine delle chiavi nel risultato persiste. Per esempio. se A[i] == A[j] == A[k] and i < j < k nell'array originale, tutte queste proprietà rimangono nell'intero array dopo aver eseguito l'algoritmo Unique. (Anche se A[i] potrebbe essere nel subarray univoco e entrambi A[j] e% A[k] si trovano nel sottoarray dei duplicati.)
Il mio tentativo fallito è un one-pass che traccia l'attuale elemento univoco mentre itera attraverso l'array. Il prossimo elemento univoco viene scambiato con l'elemento dopo la fine del subarray unico corrente:
def Unique1(A):
if len(A) <= 1:
return 0
i = 0
for j in range(1, len(A)):
if A[i] < A[j]:
i += 1
if i < j:
A[i], A[j] = A[j], A[i]
return i + 1
Scambia i primi elementi univoci di un array ordinato all'inizio dell'array, viene eseguito in un unico passaggio (quindi è O(n) ) ed è stabile per il sottoarray univoco, ma questo fa non soddisfa i requisiti perché rimescola il subarray dei duplicati:
>>> A = [1, 1, 2, 2, 3, 3, 4, 4, 5, 5]
>>> r = Unique1(A)
>>> A[r:] # duplicates part
[3, 2, 4, 1, 5] # not sorted
Mentre le modifiche apportate dall'algoritmo al subarray univoco sono alquanto ovvi, non posso "vedere" cosa sta succedendo al subarray dei duplicati, ma ho la sensazione che potrebbe essere invertito se avessimo saputo o memorizzato più informazioni sul duplicati.
Nota, riordinare solo il sottoarray duplicato è un non-starter perché 1: è O(n log n) non O(n) e 2: interrompe la stabilità.
Posso anche pensare ad un altro algoritmo che scambia elementi unici trovati di recente fino alla posizione successiva. Pur soddisfacendo le altre condizioni, avrebbe O(n^2) swap.
È possibile un algoritmo così unico? E se no, perché no?