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

Как удалить одинаковые данные из отсортированного массива

7 мая 20217 мая 2021

119

2 мин

Источник: Nuances of Programming Задача Имеется отсортированный массив nums. Необходимо удалить из него одинаковые данные так, чтобы один элемент появлялся только один раз и возвращал новое число элементов. Не нужно выделять дополнительное пространство для другого массива — необходимо произвести эту операцию путем изменения введенного массива с помощью дополнительной памяти O(1). Пример 1: Ввод:nums = [1,1,2] Вывод: 2, nums = [1,2] Объяснение: функция должна возвращать число элементов = 2, где первые два элемента — соответственно 1 и 2. Неважно, что остаётся сверх возвращенного числа элементов. В этой конкретной задаче в условиях не оговаривалось изменение введенного массива, и существовало более быстрое решение, которое возвращало бы число элементов нового массива. Однако необходимо получить отсортированный массив вместе с его числом элементом, поэтому мы пойдем дальше. Рекурсия Для этого введем понятие рекурсии — метода решения проблемы, где результат зависит от подхода к более

Оглавление

Задача
Рекурсия
Код

Источник: Nuances of Programming

Задача

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

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

Пример 1:

Ввод:nums = [1,1,2]

Вывод: 2, nums = [1,2]

Объяснение: функция должна возвращать число элементов = 2, где первые два элемента — соответственно 1 и 2. Неважно, что остаётся сверх возвращенного числа элементов.

В этой конкретной задаче в условиях не оговаривалось изменение введенного массива, и существовало более быстрое решение, которое возвращало бы число элементов нового массива. Однако необходимо получить отсортированный массив вместе с его числом элементом, поэтому мы пойдем дальше.

Рекурсия

Для этого введем понятие рекурсии — метода решения проблемы, где результат зависит от подхода к более мелким задачам. Так, вы создаёте функцию, которая решает базовую задачу, и эта рекурсивная функция будет вызывать сама себя необходимое количество раз для решения основной проблемы.

В данном случае базовым вопросом было сравнение двух чисел в массиве и удаление одного из них в случае, если они имеют одинаковое значение.

Код

Рекурсивная функция

Функция принимает два аргумента — current (позиция текущего числа, начиная с 0) и nums (отсортированный массив).

Сперва необходимо убедиться, что текущее число не является последним элементом массива, так как достигнув конца массива, мы можем вернуть число его элементов.

if (current === nums.length-1) { return nums.length;}

Как только мы узнаем, что не находимся в конце массива, можем сравнить текущее значение со следующим:

if (nums[current]!==nums[current+1])

Если текущее значение не равно следующему, вызываем функцию для следующего элемента массива, передавая следующий порядковый номер.

dups(current+1,nums);

В противном случае мы удаляем повторяющееся значение и вызываем функцию дублирования для того же элемента массива и обновленного массива.

nums.splice(current+1,1);
dups(current,nums)

Каждый раз, когда вызывается функция dups, необходимо проверить, не достигли ли мы конца массива, и когда мы очистим массив, число его элементов будет возвращено. Это лишь один из возможных примеров построения рекурсивной функции.