Решение задачи 26 “Remove Duplicates from Sorted Array” с LeetCode.

Условие задачи

Дан отсортированный массив чисел nums. Необходимо удалить дубликаты внутри этого массива и вернуть новую длину массива. Нельзя выделять место для нового массива.

пример 1

nums = [1,1,2],

Функия должна вернуть `2`. То есть нулевой и первые элемент массива должны быть `1` и `2` соответственно.

Неважно что будет дальше в массиве 

пример 2

nums = [0,0,1,1,1,2,2,3,3,4],

Функия должна вернуть `5`. первый пять элементов массива должны быть 0,1,2,3,4 и 5.

Неважно что будет дальше в массиве 

Решение

Два указателя

Идея алгоритма:

Есть два укателя:

• первый смотрит на текущий элемент ( на каждом шаге он сдвигается на следующий элемент)
• второй смотрит на последний неповторяющийся элемент

Когда элементы по текущему указателю станет больше элемента по второму указателю:

• сместить второй указатель на следующий элемент
• присвоить в адрес второго указателя значение из текущего указателя

Вернуть второй указатель + 1

func removeDuplicates(nums []int) int {
    if len(nums) <=1 {
         return len(nums) 
    }
    lidx :=0
    
    for idx:=1;idx <len(nums);idx++ {
        if nums[idx] > nums[lidx] {
             lidx ++ 
            nums[lidx] = nums[idx]
           
        }
    }
    
    return lidx+1
}