LeetCode刷题实战47：全排列 II
程序IT圈
共 6115字，需浏览 13分钟
·
2020-09-24 07:53
算法的重要性，我就不多说了吧，想去大厂，就必须要经过基础知识和业务逻辑面试+算法面试。所以，为了提高大家的算法能力，这个公众号后续每天带大家做一道算法题，题目就从LeetCode上面选 ！
今天和大家聊的问题叫做 全排列II，我们先来看题面：
https://leetcode-cn.com/problems/permutations-ii/
Given a collection of numbers that might contain duplicates, return all possible unique permutations.
题意
样例
输入: [1,1,2]
输出:
[
[1,1,2],
[1,2,1],
[2,1,1]
]
解题
无脑解决
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
回溯法
，一个是
，我们会发现对于两个位置，我们先放第一个再放第二个和先放第二个再放第一个是重复的。
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
改进
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
上期推文：
评论