`
huntfor
  • 浏览: 201546 次
  • 性别: Icon_minigender_1
  • 来自: 杭州
社区版块
存档分类
最新评论

[leetcode]Permutations II

 
阅读更多

新博文地址:[leetcode]PermutationsII

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].

 排列的题应该是很熟悉的,不熟悉的可以看这几道题:PermutationsNext Permutation, 其实,求排列的算法大致一样,这不过这道题要求可以有重复数字,求唯一的排列组合。

说起唯一,自然想起Set,我的算法也完全依赖于set,即,在生成排列序列的时候,先检查一下是否已经存在了,如果存在就不需要返回了。set的key很自然的选择用数组的String表达,遗憾的是,空间复杂度略大......

 

 

 private String getString(List<Integer> list){
	StringBuilder sb = new StringBuilder();
		for(int i : list){
			sb.append(i);
		}
		return sb.toString();
	}
	public List<List<Integer>> permuteUnique(int[] num) {
		Set<String> set = new HashSet<String>();
		List<List<Integer>> result = new ArrayList<List<Integer>>();
		if (num == null || num.length == 0) {
			return result;
		}
		if (num.length == 1) {
			List<Integer> list = new ArrayList<Integer>();
			list.add(num[0]);
			result.add(list);
			return result;
		}
		int[] pre = Arrays.copyOf(num, num.length - 1);
		List<List<Integer>> prePer = permuteUnique(pre);
		for (List<Integer> list : prePer) {
			for (int i = 0; i <= list.size(); i++) {
				List<Integer> newList = new ArrayList<Integer>();
				for(int j = 0; j < i ;j ++){
					newList.add(list.get(j));
				}
				newList.add(num[num.length - 1]);
				for(int j = i; j < list.size(); j++){
					newList.add(list.get(j));
				}
				if(!set.contains(getString(newList))){
					set.add(getString(newList));
					result.add(newList);
				}
			}
		}
		return result;
	}

 

分享到:
评论

相关推荐

Global site tag (gtag.js) - Google Analytics