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



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

Задача

Имеется отсортированный массив 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, необходимо проверить, не достигли ли мы конца массива, и когда мы очистим массив, число его элементов будет возвращено. Это лишь один из возможных примеров построения рекурсивной функции.



56   0  
    Ничего не найдено.

Добавить ответ:
Отменить.