Permutations II 典型去重
https://leetcode.com/problems/permutations-ii/
Given a collection of numbers that might contain duplicates, return all possible unique permutations.
For example,[1,1,2]
have the following unique permutations:[1,1,2]
, [1,2,1]
, and [2,1,1]
.
解题思路:
这题是 Permutations 的后续,不同之处在于,数组里可能有重复的数字。要求不能出现重复的排列,而不是排列里不能有重复的数字。
虽然这个类型的题目出现过很多次,但是这里去重的方法和前面还是有很大不同的。
首先,既然是排列,已经使用过的数字不能在当前排列中再次使用,所以要用一个数组visited来记录。
其次,如何避免题目里1,1,2这样的重复排列问题?当然首先要排序。
核心思想就是,在第i位上,上次已经选择过k,下次就不能再选k了。注意是同一个位置上的选择,而不是往下的递归,这个操作无法借助visited数组实现。如果像前面那样判断num[i]和num[i - 1]如果相等,就跳过呢?好像可以。可是遇到[1,1]这样的数组,因为num[1]==num[0],那么递归到第二步就跳出了,根本连一个排列都组成不了。如何做?
解决方法是,可以借助visited的数组。我们看到在上面的例子里,[1,1],如果num[i-1]已经被用过了,说明num[i]是本位置上第一次考虑的数字,无论他和num[i-1]是否相等,都是可以采用的。反之,如果num[i-1]还没被用过,说明num[i]是该位置上至少第二次考虑的元素了,并且前面考虑的就是num[i-1]。这时候,如果num[i]==num[i-1],就必须跳过此次选择。否则,等于一个位置上两次考虑一样的数字,肯定会有重复排列的。
代码如下:
public class Solution {
public List<List<Integer>> permuteUnique(int[] num) {
List<List<Integer>> result = new LinkedList<List<Integer>>();
if(num.length == 0) {
return result;
}
Arrays.sort(num);
int[] visited = new int[num.length];
dfs(num, result, new LinkedList<Integer>(), visited);
return result;
} public void dfs(int[] num, List<List<Integer>> result, List<Integer> current, int[] visited) {
if(current.size() == num.length) {
result.add(new LinkedList(current));
return;
}
for(int i = 0; i < num.length; i++) {
if(visited[i] == 1) {
continue;
}
if(i > 0 && num[i] == num[i - 1] && visited[i - 1] == 1) {
continue;
}
visited[i] = 1;
current.add(num[i]);
dfs(num, result, current, visited);
current.remove(current.size() - 1);
visited[i] = 0;
}
}
}
总结一下排列组合的问题,去重的思路。
同一个排列或组合中,不能出现同一个位置上的数字,借助visited数组。
同一个排列或组合中,数组从小到大排列,必须对原数组排序,并且借助step,每次递归从step开始往后。
原数组有重复数字,同一个排列或组合中,允许出现重复数字,但是排列不允许重复,比较当前数字和前一个数字,如果相等则跳过。
最新文章
- Sharepoint学习笔记—习题系列--70-576习题解析 -(Q147-Q151)
- C# treeview 绑定数据 【转】
- ruby中excel简单操作以及文件读取操作方法
- Python 3 与 MySQL 5.6
- JSP中显示用户信息
- Intersection of Two Linked Lists | LeetCode
- jQuery(Keep for myself)
- mysql中sql语句执行时间
- 使用HashMap须要注意的事儿:不要暴露Map.entry给外部不可信代码Map.entrySet()
- C1FlexGrid小结(转自http://www.cnblogs.com/C1SupportTeam/archive/2012/12/11/2812316.html)
- 树莓派Raspberry实践笔记-简单方法安装minicom
- require.js简单入门
- python模拟面试技术题答案
- iOS视频流开发(2)—视频播放
- 解决nginx access日志中400 bad request 错误(转)
- MyCat分库分表入门
- linux输入子系统
- ios下元素溢出设置 overflow:auto; 不能滑动解决办法
- bzoj 4881 [Lydsy1705月赛]线段游戏
- sql server实用要点全解