let 46 Permutations

本文主要是介绍let 46 Permutations，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

Given a collection of distinct numbers, return all possible permutations.For example,
[1,2,3] have the following permutations:
[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]
]

主题思想： 就是排列
排列算法，已经知道了，这里只需要注意处理下，什么时候到达边界，需要停止就好了。

这道题的收获， 就是无法把 一个 int[] 通过Arrays.asList() 转化为List<Integer> 只能通过先创建List<Integer> 然后一个一个添加的方式创建

先贴下根据一个数列生成下一个最小的permutation的算法，
从后往前找，找到最先出现的一个i,j 是nums[i]

 //return false if has next public boolean nextPermute(List<List<Integer>> ans,int [] nums){int n=nums.length;int i=0,j=0;//the flag which means whether has next permuateboolean flag=true;// find the index i is the first time where nums[i]<nums[j]for(j=n-1;j>=1;j--){i=j-1;if(nums[i]<nums[j]){flag=false;break;  } }if(flag) return flag;//find the index j where nums[j] > nums[i];for(j=n-1;j>i;j--){if(nums[j]>nums[i]) break;}//swap i,jswap(nums,i,j);//reverse from the i+1 to the endreverse(nums,i+1,n-1);List<Integer> tmp=new ArrayList<Integer>();for(int num: nums)  tmp.add(num);ans.add(tmp);return flag;}public void swap(int[] nums,int i,int j){int t=nums[i];nums[i]=nums[j];nums[j]=t;return ;}public void reverse(int []nums,int low,int hi){if(hi<=low) return ;while(low<hi){swap(nums,low,hi);low++;hi--;}return ;}

最后AC代码：

class Solution {public List<List<Integer>> permute(int[] nums) {List<List<Integer>> ans=new ArrayList<List<Integer>>();if(nums==null||nums.length<1) return ans;Arrays.sort(nums);List<Integer> tmp=new ArrayList<Integer>();for(int i: nums) tmp.add(i);ans.add(tmp);int n=nums.length;if(n==1) return ans;boolean flag=false;while(!flag){flag=nextPermute(ans,nums);}return ans;//}//return false if has next public boolean nextPermute(List<List<Integer>> ans,int [] nums){int n=nums.length;int i=0,j=0;//the flag which means whether has next permuateboolean flag=true;// find the index i is the first time where nums[i]<nums[j]for(j=n-1;j>=1;j--){i=j-1;if(nums[i]<nums[j]){flag=false;break;  } }if(flag) return flag;//find the index j where nums[j] > nums[i];for(j=n-1;j>i;j--){if(nums[j]>nums[i]) break;}//swap i,jswap(nums,i,j);//reverse from the i+1 to the endreverse(nums,i+1,n-1);List<Integer> tmp=new ArrayList<Integer>();for(int num: nums)  tmp.add(num);ans.add(tmp);return flag;}public void swap(int[] nums,int i,int j){int t=nums[i];nums[i]=nums[j];nums[j]=t;return ;}public void reverse(int []nums,int low,int hi){if(hi<=low) return ;while(low<hi){swap(nums,low,hi);low++;hi--;}return ;}
}

这篇关于let 46 Permutations的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---