Эта статья возникла из личного публичного аккаунта:TechFlow, оригинальность это не просто, прошу внимания
СегодняТемы LeetCodeВ 49-й статье давайте рассмотрим 80-й вопрос LeetCode «Удалить дубликаты из отсортированного массива II».
Официальная сложность этого вопроса — средняя, а проходной балл — 43,3%, 1104 лайка и 690 отклонений. Скорость прохождения этого вопроса немного высока, а коэффициент лайков не очень высок. объясни этолегкий, и оценка у всех низкая. Это действительно так, я лично думаю, что основная причина плохой оценки в том, что этот вопрос немного проще.
тема
На самом деле мы уже можем получить много информации из названия вопроса, и на самом деле это правда.Название этого вопроса тесно связано с названием, нам нужнодедуплицировать упорядоченный массив. Однако условие дедупликации состоит в том, чтобы позволить одному элементу появляться не более двух раз, то есть удалить избыточные элементы. И название также ограничивает необходимость работы с исходным массивом, а требования к пространственной сложности таковы.
. Поскольку длина массива изменится после удаления элементов, нам, наконец, нужно вернуть длину массива после завершения.
Это нормальная практика,В C++ и некоторых старых языках массивы не могут быть изменены по длине.. Если мы хотим удалить данные в исходном массиве, мы можем только переместить удаляемые данные в конец массива, а затем вернуть длину массива после изменения. Таким образом, нисходящий поток может узнать изменение количества после изменения через длину возвращаемого массива. Поскольку некоторые новые языки, такие как Java и Python, поддерживают изменение длины массива, такое использование редко встречается в коде этих языков.
Образец
Given nums = [0,0,1,1,1,1,2,3,3],
Your function should return length = 7, with the first seven elements of nums being modified to 0, 0, 1, 1, 2, 3 and 3 respectively.
It doesn't matter what values are set beyond the returned length.
В этом примере, поскольку 1 встречается 4 раза, мыНужно удалить 2 1s, то длина массива после удаления также уменьшится на 2, поэтому нам нужно вернуть 7, указав, что эффективная длина нового массива после удаления равна 7. И убедитесь, что первые 5 элементов в исходном массиве равны [0, 0, 1, 1, 2, 3]
отвечать
Удаление повторяющихся элементов само по себе не сложно, проблема только в том, как намСделайте это, не вводя дополнительное хранилище. Если вы можете понять тот факт, что массивы упорядочены, это должно быть легко понять: поскольку массивы упорядочены, одни и те же элементы должны быть размещены вместе.
Так как одни и те же элементы выстраиваются вместе, то мы можемИспользуйте переменную для хранения того, сколько раз появляется текущий элемент. Если встречается другой элемент, установите счетчик равным 1. Таким образом, мы можем определить, какие элементы нужно удалить, а какие сохранить.
Но это создает другую проблему: как удалить эти повторяющиеся элементы? Поскольку мы не можем ввести дополнительные массивы, это необходимо сделать для текущего массива. Мы можем начать с предположения, что такого ограничения нет, что бы мы сделали?
new_nums = []
cur = None
for i in range(n):
if cur == nums[i]:
count += 1
else:
count = 1
cur = nums[i]
if count > 2:
continue
new_nums.append(nums[i])
Из-за этого ограничения все, что нам нужно сделать, этоУдалить массив new_nums, На самом деле, это очень просто удалить, потому что мы можем позволить массиву nums покрыть себя. Поскольку объем выходных данных должен быть меньше или равен длине массива, проблемы с выходом за границы массива не возникнет. Нам нужно только поддерживать индекс для записи позиций в массиве nums, которые разрешено перезаписывать.
Это тоже очень распространенная практика, и мы видели ее в предыдущих темах.
class Solution:
def removeDuplicates(self, nums: List[int]) -> int:
# start是起始覆盖指针，指向第一个可以覆盖的位置
start, cur, cnt = 0, None, 0
n = len(nums)
if n == 0:
return 0
for i in range(n):
if cur == nums[i]:
cnt += 1
else:
cnt = 1
cur = nums[i]
# 如果数量超过2，说明当前元素应该舍弃，则continue
if cnt > 2:
continue
# 否则用当前元素覆盖start位置，并且start移动一位
else:
nums[start] = nums[i]
start += 1
return start
Также существует упрощенная версия этого кода, мы также можем опустить переменную cnt. Поскольку элементы упорядочены, мы можем напрямую использовать nums[i] и nums[i-2] для оценки.Если они равны, это означает, что должно быть более двух повторяющихся элементов, и текущий элемент нужно пропустить.
Упрощенный код выглядит следующим образом:
class Solution(object):
def removeDuplicates(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
i = 0
for n in nums:
if i < 2 or n != nums[i - 2]:
nums[i] = n
i += 1
return i
Суммировать
Сегодняшний вопрос не сложный, и вообще говоря, он считается низким уровнем сложности на Medium.Есть два основных момента, заслуживающих похвалы. Первый пункт — это метод замены массива на месте в стиле C++, а второй пункт — метод самозатирания массива. К тому же задача почти не сложная, думаю каждый сможет придумать решение.
Если вам понравилась эта статья, пожалуйстаобращать внимание, подбодрите меня и облегчите доступ к другим статьям.
В этой статье используетсяmdniceнабор текста