Эта статья возникла из личного публичного аккаунта:TechFlow, оригинальность это не просто, прошу внимания
СегодняLeetCode 28thЭто по-прежнему проблема всей маршрутизации.
Если вы не знакомы с полной расстановкой или в последнее время беспокоитесь о студентах, вы можете прочитать предыдущую статью:
Алгоритм возврата LeetCode46 для полной перестановки, на этот раз это истинная полная перестановка
LeetCode нравится это, собирайте похожие проблемы вместе, позволяйте вам сталкиваться вместе, когда вы чистите, чтобы понять более глубоко. Сегодняшняя задача тоже полная перестановка, но небольшое отличие в том, что у нас другое ограничение,В данных элементах могут быть дубликаты. Но элементы повторяются, и мы не хотим, чтобы конечный результат повторялся, что нам делать в это время?
Например, допустим, у нас есть перестановка [1, 2, 2].
Все его перестановки — это [1, 2, 2], [2, 1, 2], [2, 2, 1], но обратите внимание, что в предыдущем подходе мы рассматривали все элементы как уникальные, но сейчас это условие нарушено. Очевидно, нам нужно решить эту задачу на основе реализации полной перестановки.
Безмозглое решение
Есть два решения, первоеБезмозглое решение. Да, вы правильно прочитали, потому что мы анализируем это и узнаемnext_permutationМетод цикла все еще работает в этой задаче, и причина очень проста, потому что каждый раз, когда мы используем next_permutation для поиска следующей перестановки лексикографического порядка + 1, очевидно, что повторяющиеся элементы были удалены. Зачем? Поскольку лексикографический порядок изменения позиции одного и того же элемента не изменится.
Например, на рисунке ниже мы заменяем порядок двух двоек, а лексикографический порядок всей последовательности не меняется.Чтобы изменить лексикографический порядок, нужно поменять местами разные элементы. Так что это решение осуществимо.
next_permutation - вернуть текущую последовательностьлексикографический порядок +1Алгоритм последовательности , этот алгоритм появился в предыдущей статье, поэтому я не буду повторять его принцип, если вы не помните или забыли, вы можете перейти по ссылке ниже для ознакомления:
LeetCode 31: рекурсия, возврат, восемь ферзей, полная перестановка
Это решение точно такое же, как последнее решение предыдущего вопроса, и нам даже не нужно его менять, мы можем просто скопировать код и сопоставить имя функции, чтобы отправить его. Вот почему я говорю, что этот вопрос глупый.
class Solution:
def get_next(self, nums: List[int]):
"""
Do not return anything, modify nums in-place instead.
"""
# 长度
n = len(nums)
# 记录图中i-1的位置
pos = n - 1
for i in range(n-1, 0, -1):
# 如果降序破坏,说明找到了i
if nums[i] > nums[i-1]:
pos = i-1
break
for i in range(n-1, pos, -1):
# 从最后开始找大于pos位置的
if nums[i] > nums[pos]:
# 先交换元素,在进行翻转
nums[i], nums[pos] = nums[pos], nums[i]
# 翻转[pos+1, n]区间
nums[pos+1:] = nums[n:pos:-1]
return False
return True
def permuteUnique(self, nums: List[int]) -> List[List[int]]:
ret = []
# 从小到大排序,获得最小排列
nums = sorted(nums)
ret.append(nums.copy())
# 如果还有下一个排列则继续调用
while not self.get_next(nums):
# 要.copy()是因为Python中存储的引用,如果不加copy
# 会导致当nums发生变化之后,ret中存储的数据也会变化
ret.append(nums.copy())
return ret
Возвращение
Очевидно, что повторение предыдущей работы не делает нас сильнее, поэтому мы вернемся к правильному ответу. Как мы знаем из предыдущей статьи, создание полностью переставленногоОбычной практикой является использование обратного отслеживания. Так как же решить проблему дублирования элементов, если мы используем поиск с возвратом?
Или старая практика, мы должны сначала решить проблемуанализировать проблему, мы знаем, что повторяющиеся элементы будут мешать алгоритму генерации полной перестановки, так почему же он мешает и как он мешает?
При возврате мы последовательно обходим позиции, а затем перечисляем размещенные элементы. Таким образом, мы, вероятно, можем представить себе две ситуации, которые могут привести к дублированию.
Давайте сначала рассмотрим случай 1. Случай 1 очень прост, т.е.Поместите тот же элемент в ту же позициюСлучай. Например, в нашем исходном массиве есть две четверки, и ситуация, когда мы помещаем первую четверку и вторую четверку в процессе размещения, одинакова. Очевидно, это повторяется. Мы можем обратиться к следующему рисунку. Мы пронумеровали все варианты выбора в данный момент. Вариант 2 и вариант 3 эквивалентны, и только один из двух может быть выбран.
Второй случай тоже проще для понимания, это тот же пример, мы пронумеровали две четверки в массиве, и одна цифра,один
, найдем, что для обеих позиций мыПоложение первого, затем второго и повторение второго, а затем первого.
На первый взгляд это две ситуации, но если вы проанализируете их глубже, вы обнаружите, что эти две ситуации на самом деле означают одно и то же.нестабильныйВызванный.
здесь"стабильность«На самом деле это термин в алгоритмах сортировки. Мы часто обсуждаем, что алгоритм сортировки стабилен, а какой-то нет. Что это значит?относительный порядок элементов. Например, для двух 4 на приведенном выше рисунке, если последние 4 могут появиться перед первыми 4 в отсортированном результате, это означает, что алгоритм нестабилен. Точно так же, если этого не происходит, то алгоритм может быть говорят стабильно.
Опять же, если мы можем гарантировать стабильность элементов при выполнении полной перестановки, то эта проблема решена. На первый взгляд это кажется проблемой оптимизации, но на самом деле это не так, рассматривается понятие стабильности.
Если вы можете думать о стабильности, это очень близко к решению. Нам нужно обеспечить стабильность, то есть для текущего элемента нам нужно убедиться, что предыдущий такой же элемент был размещен, затемВ аранжировке размещение одного и того же элемента должно быть последовательным.. Мы используем карту для записи последней позиции каждого элемента и управляем ее увеличением в рекурсивном процессе.
Например, когда в массиве две четверки, если первая четверка не размещена, то и вторая четверка не может быть размещена. Но так как мы не знаем, есть ли перед нами другие четверки, когда судим, ставить ли вторую четверку, мы можем только перевернуть ее,Определить, были ли следующие 4 выброшены при размещении первых 4, если он есть, то эту операцию выполнить нельзя. Немного сложно описать эту логику на языке.Давайте посмотрим на следующий рисунок, чтобы понять:
После того, как мы разместили первые 4, map[4] = 4, что записывает индекс размещенных 4. Когда мы перечисляем и размещаем первые 4, мы обнаруживаем, что индекс размещенных 4 больше, чем текущий. является незаконным, и его размещение приведет к повторению.
Другая проблема заключается в том, что когда мы возвращаемся назад,Нужно сбросить значение в карте,Например:
В рекурсии мы разместили две четверки, а после размещения второй четверки map[4] = 4. Когда мы вернулись и вытолкнули вторую четверку, какой должна быть карта[4] в это время?
Ответ не сложный, он должен быть 1, который является нижним индексом первых 4. Поэтому, когда мы рекурсивно, перед обновлением карты,Необходимо записать предыдущее значение, который удобно восстанавливать при возврате.
Давайте разберемся, идея может получить код:
class Solution:
def dfs(self, nums, n, i, states, cur, ret, flag):
if i == n:
ret.append(cur.copy())
return
for p in range(n):
# 遍历所有元素
# 如果p元素已经放置过了,或者是已经放置了更后面的同元素
# 跳过
if flag[p] or (nums[p] in states and states[nums[p]] >= p):
continue
# 当前位置放置p
cur.append(nums[p])
# 更新之前,记录之前的值
tmp, states[nums[p]] = states[nums[p]] if nums[p] in states else -1, p
# flag[p]置为True
flag[p] = True
# 递归
self.dfs(nums, n, i+1, states, cur, ret, flag)
# 回溯
cur.pop()
flag[p] = False
# 恢复递归之前的值
states[nums[p]] = tmp
# states.remove((i, nums[p]))
def permuteUnique(self, nums: List[int]) -> List[List[int]]:
ret = []
n = len(nums)
# 记录元素i有没有放置过
flag = [False for _ in range(n)]
self.dfs(nums, n, 0, {}, [], ret, flag)
return ret
Улучшать
Вышеупомянутый метод на самом деле немного сложен для пониманиямного деталей, Один из самых болезненных моментов, это то, что мы используем карту для записи положения.Так как карту необходимо обновить, нам также необходимо записать предыдущее значение, а также нам нужно судить о ситуации, что элемент не находится в карта. И поиск по карте имеет накладные расходы, поэтому мы можем не использовать карту?
Прежде чем думать об альтернативах использованию карты, нам нужно выяснить, почему мы используем карту?
Этот вопрос не достаточный вопрос, а необходимый вопрос,Дело не в том, что карта используется для решения любой проблемы, но почему мы не можем использовать только карту?
Поскольку карта является контейнером, она может хранить данные. Для элемента t мы не знаем, где он появился раньше в массиве nums, и мы не знаем, были ли эти предыдущие t помещены в текущий массив. Мы используем карту для записи нижнего индекса t, основная причина в этом. map — это просто средство для достижения этой функции, а не цель.
Поэтому, если мы не хотим использовать карту, мы должныУбедитесь, что вы знаете, где находится каждый элементТолько тогда может. Это не сложно сделать, нам просто нужно отсортировать числа. После сортировки все одинаковые элементы располагаются рядом друг с другом. Тогда для позиции p нам нужно только судить, что если nums[p-1] равно nums[p], flag[p-1] должен быть равен true, то есть для элемента v он имеет один бит перед ним. Если v должен быть помещен, текущий v может быть помещен, в противном случае это недопустимо. Таким образом, каждая v ограничивает предыдущую v, что гарантирует, что все v не будут конфликтовать. Этопредел цепочкиподумал о.
Таким образом, мы можем отказаться от использования карты, тем самым значительно повысив эффективность.
Если подумать над принципом, код очень прост:
class Solution:
def dfs(self, nums, n, i, cur, ret, flag):
if i == n:
ret.append(cur.copy())
return
for p in range(n):
# 遍历所有元素
# 如果p元素已经放置过了,或者
# 如果nums[p-1] == nums[p] 并且flag[p-1] 是False
# 跳过
if flag[p] or (p > 0 and nums[p-1] == nums[p] and not flag[p-1]):
continue
# 当前位置放置p
cur.append(nums[p])
# flag[p]置为True
flag[p] = True
# 递归
self.dfs(nums, n, i+1, cur, ret, flag)
# 回溯
cur.pop()
flag[p] = False
def permuteUnique(self, nums: List[int]) -> List[List[int]]:
ret = []
n = len(nums)
# 记录元素i有没有放置过
nums = sorted(nums)
flag = [False for _ in range(n)]
self.dfs(nums, n, 0, [], ret, flag)
return ret
ты видишь мыпросто нужно отсортировать, и не нужно вводить новую структуру данных, он прекрасно решает эту проблему. На самом деле во многих случаях существует множество способов решения проблемы, и то, сможете ли вы придумать лучшее решение, зависит не только от ваших способностей, но и от вашего понимания проблемы.
Этот вопрос также являетсяMediumЗадача в целом не сложная. Если вы можете пройти этот вопрос самостоятельно, не заглядывая в стандартную программу, значит, мышление по проблеме полной перестановки на месте.
На сегодняшней статье все. Если вы чувствуете, что что-то приобрели, пожалуйста, нажмитеПодпишитесь или сделайте ретвитЧто ж, твое маленькое усилие много значит для меня.