Задача
Имеется отсортированный массив nums. Необходимо удалить из него одинаковые данные так, чтобы один элемент появлялся только один раз и возвращал новое число элементов.
Не нужно выделять дополнительное пространство для другого массива — необходимо произвести эту операцию путем изменения введенного массива с помощью дополнительной памяти O(1).
Пример 1:
Ввод:nums = [1,1,2]
Вывод: 2, nums = [1,2]
Объяснение: функция должна возвращать число элементов = 2, где первые два элемента — соответственно 1 и 2. Неважно, что остаётся сверх возвращенного числа элементов.
В этой конкретной задаче в условиях не оговаривалось изменение введенного массива, и существовало более быстрое решение, которое возвращало бы число элементов нового массива. Однако необходимо получить отсортированный массив вместе с его числом элементом, поэтому мы пойдем дальше.
Рекурсия
Для этого введем понятие рекурсии — метода решения проблемы, где результат зависит от подхода к более мелким задачам. Так, вы создаёте функцию, которая решает базовую задачу, и эта рекурсивная функция будет вызывать сама себя необходимое количество раз для решения основной проблемы.
В данном случае базовым вопросом было сравнение двух чисел в массиве и удаление одного из них в случае, если они имеют одинаковое значение.
Код
var removeDuplicates = function (nums) {
if (nums.length === 0) {
return 0;
}
dups(0, nums);
function dups(current, nums) {
if (current === nums.length - 1) {
return nums.length;
} else {
if (nums[current] !== nums[current + 1]) {
dups(current + 1, nums);
} else {
nums.splice(current + 1, 1);
dups(current, nums)
}
}
};
};Рекурсивная функция
Функция принимает два аргумента — 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, необходимо проверить, не достигли ли мы конца массива, и когда мы очистим массив, число его элементов будет возвращено. Это лишь один из возможных примеров построения рекурсивной функции.
Читайте также:
- Алгоритмы ограничения скорости
- 5 типов алгоритмов машинного обучения, которые нужно знать
- Как освоить алгоритмы?
Читайте нас в Telegram, VK и Яндекс.Дзен
Перевод статьи: Nick Solonyy: How to Remove Duplicates from a Sorted Array
