Open azl397985856 opened 1 year ago
class Solution {
public:
void help(int pos,vector<vector<int>>&ans,vector<int>& nums){
if(pos>nums.size()){
return;
}
if(pos==nums.size()-1){
for(int i=0;i<ans.size();i++){
if(ans[i]==nums){
return;
}
}
ans.push_back(nums);
return;
}
for(int i=pos;i<nums.size();i++){
swap(nums[i],nums[pos]);
help(pos+1,ans,nums);
swap(nums[i],nums[pos]);
}
}
vector<vector<int>> permuteUnique(vector<int>& nums) {
vector<vector<int>>ans;
help(0,ans,nums);
return ans;
}
};
class Solution:
def permuteUnique(self, nums: List[int]) -> List[List[int]]:
res = []
path = []
used = [0] * len(nums)
nums.sort()
def backtrack(nums, used):
if len(path) == len(nums):
res.append(path[:])
return
for i in range(len(nums)):
if used[i] == 1:
continue
if i > 0 and nums[i] == nums[i -1] and used[i-1] == 0:
continue
path.append(nums[i])
used[i] = 1
backtrack(nums,used)
path.pop()
used[i] = 0
backtrack(nums, used)
return res
回溯,因为有重复数字,需要用visited记录下是否选过了。
var permuteUnique = function(nums) {
nums = nums.sort((a,b) => a-b);// 把重复的放在一起。
const res = [];
// 因为数字相同的index不同,不能简单通过值排除,所以记录index是否入选了
const visited = []
var combineFunc = function(path) {
if (path.length === nums.length) {
res.push([...path]);
return;
}
for (let i = 0;i<nums.length;i++) {
// index i 已入选则不递归,保证重复数字都能入选
if (visited[i] === 1) continue;
// 保持相同数字的顺序,前面的数字没选上,后面相同的不能选
// 避免只重复的相互交换了顺序:112和112其实是一样的
if (i !==0 && nums[i] === nums[i-1] && visited[i-1] === 0) continue;
visited[i] = 1;
path.push(nums[i]);
combineFunc([...path])
path.pop();
visited[i] = 0;
}
}
combineFunc([]);
return res;
};
时间:O(n! ) 空间:O(n! *n )
class Solution: def permuteUnique(self, nums: List[int]) -> List[List[int]]: ans = [[]] for n in nums: new_ans = [] for l in ans: for i in range(len(l)+1): new_ans.append(l[:i]+[n]+l[i:]) if i<len(l) and l[i]==n: break #handles duplication ans = new_ans return ans
code
public List<List<Integer>> permuteUnique(int[] nums) {
Arrays.sort(nums);
int n = nums.length;
List<List<Integer>> ans = new ArrayList<>(n * n);
dfs(nums, new boolean[n], new ArrayDeque<>(n), ans);
return ans;
}
private void dfs(int[] nums, boolean[] used, Deque<Integer> path, List<List<Integer>> ans) {
if (path.size() == nums.length) {
ans.add(new ArrayList<>(path));
return;
}
for (int i = 0; i < nums.length; i++) {
if (used[i]
|| (i > 0 && nums[i - 1] == nums[i] && !used[i - 1]))
continue;
used[i] = true;
path.addLast(nums[i]);
dfs(nums, used, path, ans);
path.removeLast();
used[i] = false;
}
}
class Solution:
def permuteUnique(self, nums: List[int]) -> List[List[int]]:
res = []
path = []
n = len(nums)
used = [False] * n
nums.sort()
def dfs(start: int) -> None:
if start == n:
res.append(path[:])
return
for i in range(n):
if used[i]:
continue
if i > 0 and nums[i] == nums[i-1] and not used[i-1]:
continue
path.append(nums[i])
used[i] = True
dfs(start + 1)
path.pop()
used[i] = False
dfs(0)
return res
# 1
# 1
# 2
/**
**核心在于**: 在 idx 上, 只填入 nums[i] 一次, 避免重复
Approach 2: swap: 不断把所有可选择的数 换到当前位置
TC: O(N * N!)
SC: O(N)
*/
public class Solution {
List<List<Integer>> res = new ArrayList<>();
int[] nums;
int N;
public List<List<Integer>> permuteUnique(int[] nums) {
// if (nums == null || nums.length==0)
// return res;
this.nums = nums;
this.N = nums.length;
dfs(0);
return res;
}
private void dfs(int idx) {
if (idx == N) {
List<Integer> tmp = new ArrayList<>();
for (int x: nums) { tmp.add(x); }
res.add(tmp);
return;
}
// 保证对于 在 idx 的位置上, 只会添加 nums[i] 一次
Set<Integer> used = new HashSet<>();
for (int i = idx; i < N; i++) {
if (used.add(nums[i])) {
swap(nums, idx, i);
dfs(idx + 1);
swap(nums, idx, i);
}
}
}
private void swap(int[] nums, int a, int b) {
int x = nums[a];
nums[a] = nums[b];
nums[b] = x;
}
}
/**
Approach 1: 不断 loop 整个数组, 尝试使用未被使用的数, 加在 tmp 中
如何避免重复? 在 填第idx个数时, 重复数字只填入一次
x x x
o x x
o o x
o o o
为此需要对原数组排序, 保证相同的数字都相邻,
然后每次填入的数一定是 这个数所在重复数集合 中「从左往右第一个未被填过的数字」
*/
class Solution1 {
List<List<Integer>> res = new ArrayList<>();
List<Integer> tmp = new ArrayList<>();
int[] nums;
int N;
boolean[] visited;
public List<List<Integer>> permuteUnique(int[] nums) {
this.nums = nums;
this.N = nums.length;
this.visited = new boolean[N];
Arrays.sort(nums);
dfs(0);
return res;
}
// 不断 loop 整个数组, 尝试使用未被使用的数, 加在 tmp 中
// idx 代表的是 现在讲新的数 添加进的 tmp 中的位置
private void dfs(int idx) {
if (idx == N) {
res.add(new ArrayList<>(tmp));
return;
}
for (int i = 0; i < N; i++) {
if (i > 0 && nums[i] == nums[i - 1] && visited[i - 1])
continue;
if (!visited[i]) {
visited[i] = true;
tmp.add(nums[i]);
dfs(idx + 1);
visited[i] = false;
tmp.remove(idx);
}
}
}
}
class Solution {
public:
vector<vector<int>> ans;
vector<int> index;
unordered_map<int,bool> visited;
void helper(vector<int>& nums, int level, unordered_map<int,bool>& visited){
if(level==nums.size()){
ans.push_back(index);
return;
}
for(int i=0;i<nums.size();i++){
if(visited[i]==false){
if(i>0 && nums[i]==nums[i-1]&& !visited[i - 1]){
continue;
}
visited[i]=true;
index.push_back(nums[i]);
helper(nums,level+1,visited);
index.pop_back();
visited[i]=false;
}
}
}
vector<vector<int>> permuteUnique(vector<int>& nums) {
int n = nums.size();
sort(nums.begin(),nums.end());
for(int i=0;i<n;i++){
visited[i]=false;
}
helper(nums,0,visited);
// set<vector<int>> s(ans.begin(),ans.end());
// ans.assign(s.begin(),s.end());
return ans;
}
};
O(N!∗op(res)),其中 N 是数组长度,op 操作即是昨天说的 res.add 算子的时间复杂度。 O(N∗N!)
回溯+剪枝。参考官方题解。因为我们要求排列,在排列中,每个元素只出现一次,所以我们使用一个visited数组来记录每个元素的被访问情况。去重和组合总和II的方法类似。先将数组排序,然后当遇到当前元素和之前一个元素相等并且前一个元素已经被访问过时,我们跳过当前元素。
class Solution {
public List<List<Integer>> permuteUnique(int[] nums) {
List<List<Integer>> res = new ArrayList<>();
List<Integer> list = new ArrayList<>();
boolean[] visited = new boolean[nums.length];
Arrays.sort(nums);
backtrack(nums, list, res, visited);
return res;
}
private void backtrack(int[] nums, List<Integer> list, List<List<Integer>> result, boolean[] visited) {
// if the length of list is equal to the length of nums, we find one permutation
if (list.size() == nums.length) {
result.add(new ArrayList<>(list));
return;
}
for (int i = 0; i < nums.length; i++) {
// when the current element is equal to previous element and previous element is visited
if (i > 0 && nums[i] == nums[i - 1] && visited[i - 1]) {
continue;
}
// in permutation, one element will only show up once, if this element is visited, we will skip it
// if this element is not visited, continue backtracking to add another element
if (!visited[i]) {
visited[i] = true;
list.add(nums[i]);
backtrack(nums, list, result, visited);
visited[i] = false;
list.remove(list.size() - 1);
}
}
}
}
复杂度分析
public List<List<Integer>> permuteUnique(int[] nums) {
List<List<Integer>> res = new ArrayList<>();
if (nums == null || nums.length == 0)
return res;
boolean[] visited = new boolean[nums.length];
Arrays.sort(nums);
dfs(nums, res, new ArrayList<Integer>(), visited);
return res;
}
public void dfs(int[] nums, List<List<Integer>> res, List<Integer> tmp, boolean[] visited) {
if (tmp.size() == nums.length) {
res.add(new ArrayList(tmp));
return;
}
for (int i = 0; i < nums.length; i++) {
if (i > 0 && nums[i] == nums[i - 1] && visited[i - 1])
continue;
if (!visited[i]) {
visited[i] = true;
tmp.add(nums[i]);
dfs(nums, res, tmp, visited);
visited[i] = false;
tmp.remove(tmp.size() - 1);
}
}
class Solution:
def permuteUnique(self, nums: List[int]) -> List[List[int]]:
def dfs(ans, temptlist, nums, check):
if len(temptlist) == len(nums):
return ans.append(temptlist[:])
for i in range(len(nums)):
if check[i] == 1:
continue
if i>0 and nums[i]==nums[i-1] and check[i-1] == 0:
continue
check[i] = 1
temptlist.append(nums[i])
dfs(ans,temptlist,nums,check)
temptlist.pop()
check[i] = 0
nums = sorted(nums)
temptlist = []
ans = []
check = [0]*len(nums)
dfs(ans, temptlist, nums, check)
return ans
public List<List<Integer>> permuteUnique(int[] nums) {
Arrays.sort(nums);
int n = nums.length;
List<List<Integer>> ans = new ArrayList<>(n * n);
dfs(nums, new boolean[n], new ArrayDeque<>(n), ans);
return ans;
}
private void dfs(int[] nums, boolean[] used, Deque<Integer> path, List<List<Integer>> ans) {
if (path.size() == nums.length) {
ans.add(new ArrayList<>(path));
return;
}
for (int i = 0; i < nums.length; i++) {
if (used[i]
|| (i > 0 && nums[i - 1] == nums[i] && !used[i - 1]))
continue;
used[i] = true;
path.addLast(nums[i]);
dfs(nums, used, path, ans);
path.removeLast();
used[i] = false;
}
}
/**
* @param {number[]} nums
* @return {number[][]}
*/
var permuteUnique = function(nums) {
const ans = [];
const vis = new Array(nums.length).fill(false);
const backtrack = (idx, perm) => {
if (idx === nums.length) {
ans.push(perm.slice());
return;
}
for (let i = 0; i < nums.length; ++i) {
if (vis[i] || (i > 0 && nums[i] === nums[i - 1] && !vis[i - 1])) {
continue;
}
perm.push(nums[i]);
vis[i] = true;
backtrack(idx + 1, perm);
vis[i] = false;
perm.pop();
}
}
nums.sort((x, y) => x - y);
backtrack(0, []);
return ans;
};
class Solution {
vector<int> vis;
public:
void backtrack(vector<int>& nums, vector<vector<int>>& ans, int idx, vector<int>& perm) {
if (idx == nums.size()) {
ans.emplace_back(perm);
return;
}
for (int i = 0; i < (int)nums.size(); ++i) {
if (vis[i] || (i > 0 && nums[i] == nums[i - 1] && !vis[i - 1])) {
continue;
}
perm.emplace_back(nums[i]);
vis[i] = 1;
backtrack(nums, ans, idx + 1, perm);
vis[i] = 0;
perm.pop_back();
}
}
vector<vector<int>> permuteUnique(vector<int>& nums) {
vector<vector<int>> ans;
vector<int> perm;
vis.resize(nums.size());
sort(nums.begin(), nums.end());
backtrack(nums, ans, 0, perm);
return ans;
}
};
class Solution {
List<List<Integer>> result = new ArrayList<>();
List<Integer> path = new ArrayList<>();
public List<List<Integer>> permuteUnique(int[] nums) {
boolean[] usedY = new boolean[nums.length];
backtracking(nums,usedY);
return result;
}
public void backtracking(int[] nums,boolean[] usedY){
if(path.size() == nums.length){
result.add(new ArrayList(path));
return;
}
List<Integer> usedX = new ArrayList<>();
for(int i = 0;i < nums.length;i++){
if(usedY[i] == true || usedX.contains(nums[i]))
continue;
usedX.add(nums[i]);
usedY[i] = true;
path.add(nums[i]);
backtracking(nums,usedY);
path.remove(path.size()-1);
usedY[i] = false;
}
}
}
from typing import List
class Solution:
def permuteUnique(self, nums: List[int]) -> List[List[int]]:
def dfs(nums, size, depth, path, used, res):
if depth == size:
res.append(path.copy())
return
for i in range(size):
if not used[i]:
if i > 0 and nums[i] == nums[i - 1] and not used[i - 1]:
continue
used[i] = True
path.append(nums[i])
dfs(nums, size, depth + 1, path, used, res)
used[i] = False
path.pop()
size = len(nums)
if size == 0:
return []
nums.sort()
used = [False] * len(nums)
res = []
dfs(nums, size, 0, [], used, res)
return res
47 全排列 II
入选理由
暂无
题目地址
https://leetcode-cn.com/problems/permutations-ii/
前置知识
题目描述
示例:
输入: [1,1,2] 输出: [ [1,1,2], [1,2,1], [2,1,1]