[LC] 47. Permutations II
2024-08-27 11:59:21
Given a collection of numbers that might contain duplicates, return all possible unique permutations.
Example:
Input: [1,1,2]
Output:
[
[1,1,2],
[1,2,1],
[2,1,1]
] Time: O(N!)
Space: O(N)
class Solution:
def permuteUnique(self, nums: List[int]) -> List[List[int]]:
res = []
if nums is None or len(nums) == 0:
return res
self.dfs(nums, 0, res)
return res def dfs(self, nums, level, res):
if level == len(nums):
res.append(list(nums))
return
my_set = set()
for i in range(level, len(nums)):
if nums[i] not in my_set:
my_set.add(nums[i])
nums[i], nums[level] = nums[level], nums[i]
self.dfs(nums, level + 1, res)
nums[i], nums[level] = nums[level], nums[i]
class Solution {
public List<List<Integer>> permuteUnique(int[] nums) {
List<List<Integer>> arrList = new ArrayList<>();
List<Integer> list = new ArrayList<>();
boolean[] visited = new boolean[nums.length];
Arrays.sort(nums);
helper(arrList, list, visited, nums);
return arrList;
} private void helper(List<List<Integer>> arrList, List<Integer> list, boolean[] visited, int[] nums) {
if (list.size() == nums.length) {
arrList.add(new ArrayList<>(list));
return;
}
for (int i = 0; i < nums.length; i++) {
if (visited[i] || (i > 0 && nums[i] == nums[i - 1] && !visited[i - 1])) {
continue;
}
visited[i] = true;
list.add(nums[i]);
helper(arrList, list, visited, nums);
list.remove(list.size() - 1);
visited[i] = false;
}
}
}
最新文章
- Python 之Ajax
- 查找“CDN、负载均衡、反向代理”等大型网络真实IP地址的方法
- Atitit 网络爬虫与数据采集器的原理与实践attilax著 v2
- xml文件的读写操作
- git的一个merge流程
- 安装配置Apache2.4和php7.0
- Siverlight网页应用程序中WCF通信注意事项
- hibernate的对象状态分析
- JavaSE&;&;JavaEE&;&;JavaME的区别【Java中常用的包结构】
- oracle+mybatis 使用动态Sql在要insert的字段不确定的情况下实现批量insert
- cmake简明使用指南
- 十分钟入门 Less
- linux 基本命令大全
- NAVICAT for 32位/64位 及破解工具PatchNavicat
- Android SO UPX壳问题小记
- 【python】列表&;&;元组&;&;字典
- mongoose和mongodb的几篇文章 (ObjectId,ref)
- Java 8 的新特性和改进总览
- Java-jdbc工具类DBUtils
- 处理器拦截器(HandlerInterceptor)详解