Come posso rendere il mio algoritmo rubino remove_duplicates (nums) più efficiente - array, ruby, algoritmo

Questa è la sfida di codifica: dato un array ordinato, rimuovi i duplicati sul posto in modo che ogni elemento appaia solo una volta e restituisca la nuova lunghezza.

Non allocare spazio aggiuntivo per un altro array, è necessario farlo modificando sul posto l'array di input con O (1) memoria aggiuntiva.

La mia risposta

def remove_duplicates(nums)

hash = {}

nums.each do |num|
if hash[num].nil?
hash[num] = 1
end
if hash[num] = 1
i = nums.index(num)
nums.delete(num)
nums.insert(i, num)
end
end

nums.length
end

Su leetcode la mia risposta supera 160/161 casi di test. Ma ricevo un messaggio di errore "Limite di tempo superato". L'errore dice che la mia risposta non è abbastanza efficiente per risolvere l'ultimo caso di test.

Sono un principiante e sto cercando consigli su come rendere la mia risposta più efficiente (in rubino)!

risposte:

Se non vuoi usare uno dei file integratimetodi suggeriti nei commenti, un algoritmo per farlo in O (n) Time e O (1) Space consiste nell'usare 2 indici per scorrere l'array. Il primo sarà l'indice in cui hai inserito l'ultima volta un valore univoco, il secondo è l'indice dell'elemento che stai attualmente guardando. La chiave di tutto ciò è che il file nums array è ordinato, quindi devi solo impostare il successivovalore se è maggiore del valore corrente. Non può essere minore (perché ordinato) e se è uguale all'ultimo valore inserito, non è univoco. Per esempio:

nums = [1, 1, 1, 2, 2, 3, 4, 5, 5, 5, 5, 5, 6, 7, 8, 8, 9, 10, 10]
def remove_duplicates(nums)
return 0 if !nums || nums.empty?
insertion_index = 0

1.upto(nums.length - 1) do |lookup_index|
if nums[lookup_index] > nums[insertion_index]
insertion_index += 1

nums[insertion_index] = nums[lookup_index]
end
end

# nums is currently:
# => [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 5, 5, 6, 7, 8, 8, 9, 10, 10]
insertion_index + 1
end

remove_duplicates(nums)

Il tuo valore di ritorno sarà il insertion_index + 1, perché il insertion_index è l'indice in cui è stato inserito l'ultimo valore univoco, quindi la lunghezza di un array è l'indice finale + 1.

È passato un po 'di tempo dall'ultima volta che ho creato un leetcodeproblema, ma mi sembra di ricordare in domande come queste in cui è necessario ridimensionare un array in posizione, lasciando tutto alla fine come qualunque fosse la strada da percorrere (siamo in Ruby, ma ci sono molti contributi lingue in cui non è così facile ridimensionare gli array in posizione). Sentiti libero di rimuovere i valori dalla fine (sul posto, secondo le istruzioni) se vuoi / ma se tutto ciò di cui hai bisogno è la lunghezza dell'array univoco, non dovrebbe essere necessario.