13,8 тыс подписчиков

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

4 минуты

73 прочтения

18 июля 2021

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

Дано: отсортированный массив 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:

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

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