Remove Duplicates from Sorted Array

Условие

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

Примеры

Input: nums = [1, 1, 2]

Output: 2, nums = [1, 2, _]

Explanation: Ваша функция должна возвращать k = 2, при этом первые два элемента nums будут 1 и 2 соответственно. Не имеет значения, что вы оставите после возвращаемого k (поэтому они и есть подчеркивания).

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

Output: 5, nums = [0, 1, 2, 3, 4, _, _, _, _, _]

Explanation: Ваша функция должна возвращать k = 5, при этом первые пять элементов nums будут равны 0, 1, 2, 3 и 4 соответственно. Не имеет значения, что вы оставите после возвращаемого k (поэтому они и есть подчеркивания).

Решение

fun removeDuplicates(nums: IntArray): Int {
    if (nums.isEmpty()) return 0  // Если массив пустой, сразу возвращаем 0

    var index = 1  // Указатель для новой позиции для уникального элемента

    // Проходим по массиву начиная со второго элемента
    for (i in 1 until nums.size) {
        if (nums[i] != nums[i - 1]) {  // Если текущий элемент отличается от предыдущего
            nums[index] = nums[i]  // Копируем его на новую позицию
            index++  // Сдвигаем указатель
        }
    }

    return index  // Возвращаем длину массива с уникальными элементами
}

Временная сложность

O(n), где n — количество элементов в массиве. Мы проходим по массиву только один раз.

Пространственная сложность

O(1), так как решение выполняется на месте и не требует дополнительной памяти, кроме нескольких переменных.