LeetCode  -  удаление дублей из отсортированного массива

Постановка задачи

Дано: отсортированный массив nums. Требуется удалить имеющиеся дубли, чтобы каждый элемент встречался только один раз и возвращал новую длину.

Дополнительное место для другого массива выделять нельзя: вместо этого нужно изменить имеющийся входной массив с помощью дополнительной памяти O(1).

Постановка задачи взята отсюда.

Пример 1:

Input: nums = [1, 1, 2]

Output: 2, nums = [1, 2]

Пояснение: функция должна возвращать длину = 2, причем первые два элемента nums равны 1 и 2 соответственно. Что остается вне возвращаемой длины  —  не имеет значения.

Пример 2:

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

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

Пояснение: функция должна возвращать длину = 5, причем первые пять элементов nums будут изменены на 0, 1, 2, 3 и 4 соответственно. Какие значения заданы за пределами возвращаемой длины  —  неважно.

Ограничения:

- 0 <= nums.length <= 3 * 10^4

- -10^4 <= nums[i] <= 10^4

- nums is sorted in ascending order.

nums сортируется в порядке возрастания.

Решение

Метод решения «в лоб»

В условии к задаче говорится о том, что при ее решении нужно обойтись без выделения дополнительного места. Но наш первый метод решения «в лоб» основывается на подсчете вхождений отдельных элементов и сохранении их в хеше (или объекте).

Ключом будет элемент массива, а значением  —  число, обозначающее, сколько раз элемент встречается в массиве.

Дальше хеш перебирается и ключи сохраняются в новом массиве.

Решение подразумевает дополнительное место для нового массива и нового хеша.

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

Попробуем улучшить первый метод решения, воспользовавшись преимуществами отсортированного массива. Задействуем два указателя i и j и продолжаем увеличивать jдо тех пор, пока nums[i] == nums[j].

А теперь проверим алгоритм:

- return if nums size <= 1



- set i = 0



- Loop for j = 1; j < nums.size(); j++

  - if nums[j] != nums[i]

    - i++

    - nums[i] = nums[j]



- return i + 1

Временная сложность этого подхода O(N), а пространственная O(1).

Решение на C++:

class Solution {

public:

    int removeDuplicates(vector<int>& nums) {

        if(nums.size() <= 1){

            return nums.size();

        }



        int i = 0;



        for(int j = 1; j < nums.size(); j++){

            if(nums[j] != nums[i){

                i++

                nums[i] = nums[j];

            }

        }



        return i + 1;

    }

};

Решение на Golang:

func removeDuplicates(nums []int) int {

    length := len(nums)



    if length <= 1 {

        return length

    }



    i := 0



    for j := 1; j < length; j++ {

        if nums[i] != nums[j] {

            i++

            nums[i] = nums[j]

        }

    }



    return i + 1

}

Решение на JavaScript:

var removeDuplicates = function(nums) {

    const length = nums.length;



    if( length <= 1 ){

        return length;

    }



    let i = 0;



    for(let j = 1; j < length; j++){

        if( nums[i] != nums[j] ){

            i++;

            nums[i] = nums[j];

        }

    }



    return i + 1;

};

Запустим пробный прогон алгоритма и посмотрим, как работает это решение:

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



Step 1: length = nums.size()

               = 10



Step 2: length <= 1

            10 <= 1

            false



Step 3: i = 0



Step 4: Loop for j = 1; 1 < 10

        nums[i] != nums[j]

        nums[0] != nums[1]

        0 != 0

        false



        j++

        j = 2



Step 5: Loop for j = 2; 2 < 10

        nums[i] != nums[j]

        nums[0] != nums[2]

        0 != 1

        true



        i++

        i = 1



        nums[i] = nums[j]

        nums[1] = nums[2]

        nums[1] = 1



        j++

        j = 3



Step 6: Loop for j = 3; 3 < 10

        nums[i] != nums[j]

        nums[1] != nums[3]

        1 != 1

        false



        j++

        j = 4



Step 7: Loop for j = 4; 4 < 10

        nums[i] != nums[j]

        nums[1] != nums[4]

        1 != 1

        false



        j++

        j = 5



Step 8: Loop for j = 5; 5 < 10

        nums[i] != nums[j]

        nums[1] != nums[5]

        1 != 2

        true



        i++

        i = 2



        nums[i] = nums[j]

        nums[2] = nums[5]

        nums[2] = 2



        j++

        j = 6



Step 9: Loop for j = 6; 6 < 10

        nums[i] != nums[j]

        nums[2] != nums[6]

        2 != 2

        false



        j++

        j = 7



Step 10: Loop for j = 7; 7 < 10

         nums[i] != nums[j]

         nums[2] != nums[7]

         2 != 3

         true



         i++

         i = 3



         nums[i] = nums[j]

         nums[3] = nums[7]

         nums[3] = 3



         j++

         j = 8



Step 11: Loop for j = 8; 8 < 10

         nums[i] != nums[j]

         nums[3] != nums[8]

         3 != 3

         false



         j++

         j = 9



Step 12: Loop for j = 9; 9 < 10

         nums[i] != nums[j]

         nums[3] != nums[9]

         3 != 4

         true



         i++

         i = 4



         nums[i] = nums[j]

         nums[4] = nums[9]

         nums[4] = 4



         j++

         j = 10



Step 13: Loop for j = 10; 10 < 10

         false



Step 14: return i + 1

         return 4 + 1 = 5