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

Читайте также:

• Как удалить одинаковые данные из отсортированного массива
• Лучший алгоритм решения задач по программированию на Python
• Как пройти собеседование по проектированию систем?

Читайте нас в Telegram, VK и Яндекс.Дзен

---

Перевод статьи Alkesh Ghorpade: LeetCode — Remove Duplicates from Sorted Array