Sobes.tech
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 writeIndex la 1 (primul element unic este deja la locul său).
  • Parcurgeți array-ul cu readIndex de 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ți writeIndex.

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]