26. Remove Duplicates from Sorted Array

Stanislav Gumeniuk включен в leetcode leetcode-problem

2020.04.09 Немного слов Одна минута

Содержание

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

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

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

пример 1

1
2
3
4
5


nums = [1,1,2],

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

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

пример 2

1
2
3
4
5


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

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

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

Решение

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

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

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

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

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

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

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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16


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
}