В этом посте я расскажу о решении проблемы с leetcode - Удалить элемент.

Проблема:

Для массива nums и значения val удалите все экземпляры этого значения на месте и верните новую длину.

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

Порядок элементов можно изменить. Неважно, что вы оставите за пределами новой длины.

Уточнение:

Не знаете, почему возвращаемое значение - целое число, а ваш ответ - массив?

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

Внутренне вы можете думать об этом:

// nums is passed in by reference. (i.e., without making a copy)
int len = removeElement(nums, val);
// any modification to nums in your function would be known by the caller.
// using the length returned by your function, it prints the first len elements.
for (int i = 0; i < len; i++) {
    print(nums[i]);
}

Пример 1:

Input: nums = [3,2,2,3], val = 3
Output: 2, nums = [2,2]
Explanation: Your function should return length = 2, with the first two elements of nums being 2.
It doesn't matter what you leave beyond the returned length. For example if you return 2 with nums = [2,2,3,3] or nums = [2,2,0,0], your answer will be accepted.

Пример 2:

Input: nums = [0,1,2,2,3,0,4,2], val = 2
Output: 5, nums = [0,1,4,0,3]
Explanation: Your function should return length = 5, with the first five elements of nums containing 0, 1, 3, 0, and 4. Note that the order of those five elements can be arbitrary. It doesn't matter what values are set beyond the returned length.

Ограничения:

  • 0 <= nums.length <= 100
  • 0 <= nums[i] <= 50
  • 0 <= val <= 100

Решение:

Это очень похоже на одну из предыдущих проблем с leetcode, то есть Удалить дубликаты из отсортированного массива. Единственная разница в том, что вместо удаления всех дубликатов нам нужно удалить указанное значение, то есть val

Таким образом, алгоритм остается почти таким же, за исключением сравнения. Это шаги -

  1. В качестве базового условия, если массив nums пуст, мы можем сразу вернуть 0 в качестве вывода.
  2. Мы можем перебирать массив с двумя указателями. Назовем их slow и fast и инициализируем оба значения 1, поскольку мы начнем итерацию массива со второго элемента массива.
  3. При итерации входного массива мы сравниваем текущий элемент с val.
  4. Если текущий элемент не равен val, мы сохраняем элемент с индексом fast до индекса slow и увеличиваем медленный на единицу. В остальном медленное остается прежним.
  5. Возвращайте медленно в качестве вывода, поскольку это количество различных элементов в массиве.

Вот так выглядит код

class Solution {
    public int removeElement(int[] nums, int val) {
        if (nums.length == 0) {
            return 0;
        }
        int slow = 0;
        for (int fast = 0; fast < nums.length; fast++) {
            if (nums[fast] != val) {
                nums[slow] = nums[fast];
                slow++;
            }
        }
        return slow;
    }
}

Надеюсь это поможет! Удачного кодирования! 🙂

Если вы думаете, что решение можно улучшить или что-то упускает, не стесняйтесь комментировать. Всегда есть возможности для улучшения.

Найдите решения для проблем с leetcode здесь - https://github.com/rishikeshdhokare/leetcode-problems