В этом посте я расскажу о решении проблемы с 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 ofnums
containing0
,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
Таким образом, алгоритм остается почти таким же, за исключением сравнения. Это шаги -
- В качестве базового условия, если массив
nums
пуст, мы можем сразу вернуть 0 в качестве вывода. - Мы можем перебирать массив с двумя указателями. Назовем их
slow
иfast
и инициализируем оба значения 1, поскольку мы начнем итерацию массива со второго элемента массива. - При итерации входного массива мы сравниваем текущий элемент с
val
. - Если текущий элемент не равен
val
, мы сохраняем элемент с индексом fast до индекса slow и увеличиваем медленный на единицу. В остальном медленное остается прежним. - Возвращайте медленно в качестве вывода, поскольку это количество различных элементов в массиве.
Вот так выглядит код
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