Senior
Dat un array sortat de numere care conține elemente duplicate. Este necesar să eliminați duplicatele in-place (direct în array-ul original) și să returnați dimensiunea array-ului rezultat. Exemplu: Input: nums = [0,0,1,1,1,2,2,3,3,4] Output: 5, nums = [0,1,2,3,4,_,_,_,_,_] Explicație: În acest array există 5 elemente unice. Plasați-le în primele cinci poziții ale array-ului original și returnați numărul 5. Elementele ulterioare în array-ul original pot fi orice.
sobes.tech AI
Răspuns de la AI
Pentru a elimina duplicatele dintr-un array sortat in-place, se pot folosi doi indicatori: unul pentru a parcurge array-ul, celălalt pentru poziția de scriere a elementelor unice.
Ideea:
- Inițializați
writeIndexla 1 (primul element unic este deja la locul său). - Parcurgeți array-ul cu
readIndexde la 1 până la sfârșit. - Dacă elementul curent nu este egal cu cel anterior, scrieți-l în
nums[writeIndex]și incrementațiwriteIndex.
La final, writeIndex va fi numărul de elemente unice.
Exemplu în Go:
func removeDuplicates(nums []int) int {
if len(nums) == 0 {
return 0
}
writeIndex := 1
for readIndex := 1; readIndex < len(nums); readIndex++ {
if nums[readIndex] != nums[readIndex-1] {
nums[writeIndex] = nums[readIndex]
writeIndex++
}
}
return writeIndex
}
// Utilizare:
// nums := []int{0,0,1,1,1,2,2,3,3,4}
// length := removeDuplicates(nums)
// fmt.Println(length) // 5
// fmt.Println(nums[:length]) // [0 1 2 3 4]