Удаление повторяющихся элементов из отсортированного массива с сохранением порядка

Условие

Необходимо изменить данный отсортированный массив так, чтобы:

• все повторяющиеся элементы были удалены;
• относительный порядок оставшихся элементов не изменился;
• в качестве результата вернуть количество уникальных элементов.

Ответ

Индекс записи переносит очередное число только тогда, когда оно отличается от последнего оставленного. Уникальный префикс имеет длину k.

Реализация:

func uniqueCount(nums []int) int {
    k := 0
    for _, value := range nums {
        if k == 0 || nums[k-1] != value {
            nums[k] = value
            k++
        }
    }
    return k
}

Время O(n), дополнительная память O(1). Результат находится в nums[:k], содержимое хвоста несущественно. Внешняя длина автоматически не изменяется; при необходимости вызывающий код присваивает nums = nums[:k]. Предусловие сортировки важно: одинаковые числа должны стоять рядом.