Chinaunix首页 | 论坛 | 博客
  • 博客访问: 270091
  • 博文数量: 170
  • 博客积分: 0
  • 博客等级: 民兵
  • 技术积分: 1709
  • 用 户 组: 普通用户
  • 注册时间: 2014-05-06 18:01
文章分类

全部博文(170)

文章存档

2016年(11)

2015年(130)

2014年(29)

分类: Java

2015-07-30 16:41:05

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


public class Permutations {


public static void main(String[] args) {
// TODO Auto-generated method stub


}
public List<List<Integer>> permute(int[] nums) {
   List<List<Integer>> totalseq=new ArrayList<List<Integer>>();
   if(nums==null&&nums.length==0){
    ArrayList<Integer> tmp=new ArrayList<Integer>();
    totalseq.add(tmp);
    return totalseq;
   }
   dfs(0,nums,totalseq);
   return totalseq;
}
private void dfs(int index, int[] nums, List<List<Integer>> totalseq) {
// TODO Auto-generated method stub
if(index==nums.length){
ArrayList<Integer> tmp=new ArrayList<>();
for(int i=0;i<nums.length;i++){

tmp.add(nums[i]);
}
totalseq.add(tmp);
}
else{
int temp=0;
for(int j=index;j<nums.length;j++){
temp=nums[index];
nums[index]=nums[j];
nums[j]=temp;
dfs(index+1, nums, totalseq);
temp=nums[index];
nums[index]=nums[j];
nums[j]=temp;
}
}

}
}


  public List<List<Integer>> permuteUnique(int[] num) {
ArrayList<List<Integer>> result = new ArrayList<List<Integer>>();
permuteUnique(num, 0, result);
return result;
}
 
private void permuteUnique(int[] num, int start, ArrayList<List<Integer>> result) {
 
if (start >= num.length ) {
ArrayList<Integer> item = convertArrayToList(num);
result.add(item);
}
 
for (int j = start; j <= num.length-1; j++) {
if (containsDuplicate(num, start, j)) {
swap(num, start, j);
permuteUnique(num, start + 1, result);
swap(num, start, j);
}
}
}
 
private ArrayList<Integer> convertArrayToList(int[] num) {
ArrayList<Integer> item = new ArrayList<Integer>();
for (int h = 0; h < num.length; h++) {
item.add(num[h]);
}
return item;
}
 
private boolean containsDuplicate(int[] arr, int start, int end) {
for (int i = start; i <= end-1; i++) {
if (arr[i] == arr[end]) {
return false;
}
}
return true;
}
 
private void swap(int[] a, int i, int j) {
int temp = a[i];
a[i] = a[j];
a[j] = temp;
}

阅读(860) | 评论(0) | 转发(0) |
0

上一篇:Maximum Subarray

下一篇:N-Queens

给主人留下些什么吧!~~