*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], and [3,2,1].

 

解法一：

the basic idea is, to permute n numbers, we can add the nth number into the resultingList<List<Integer>> from the n-1 numbers, in every possible position.

For example, if the input num[] is {1,2,3}: First, add 1 into the initial List<List<Integer>> (let's call it "answer").

Then, 2 can be added in front or after 1. So we have to copy the List in answer (it's just {1}), add 2 in position 0 of {1}, then copy the original {1} again, and add 2 in position 1. Now we have an answer of {{2,1},{1,2}}. There are 2 lists in the current answer.

Then we have to add 3. first copy {2,1} and {1,2}, add 3 in position 0; then copy {2,1} and {1,2}, and add 3 into position 1, then do the same thing for position 3. Finally we have 2*3=6 lists in answer, which is what we want.

public List<List<Integer>> permute(int[] num) { List<List<Integer>> ans = new ArrayList<List<Integer>>(); if (num.length ==0) return ans; List<Integer> l0 = new ArrayList<Integer>(); l0.add(num[0]); ans.add(l0); for (int i = 1; i< num.length; ++i){ List<List<Integer>> new_ans = new ArrayList<List<Integer>>(); for (int j = 0; j<=i; ++j){ for (List<Integer> l : ans){ List<Integer> new_l = new ArrayList<Integer>(l); new_l.add(j,num[i]); new_ans.add(new_l); } } ans = new_ans; } return ans; }

reference：https://leetcode.com/discuss/19510/my-ac-simple-iterative-java-python-solution

 

解法二：经典的recursion

 

 https://www.youtube.com/watch?v=KBHFyg2AcZ4

swap算法，时间复杂度 O(n!)

public class Solution { List<List<Integer>> res = new ArrayList<List<Integer>>(); public List<List<Integer>> permute(int[] nums) { int k = 0; int m = nums.length-1; perm(nums,k,m); return res; } public void perm(int[] nums, int k, int m) { if(k==m) { List<Integer> list = new ArrayList<Integer>(); for(int i=0;i<=m;i++) { list.add(nums[i]); } res.add(list); } else for( int i=k; i<=m; i++) { swap(nums,k,i); perm(nums, k+1, m); swap(nums,k,i); } } public int[] swap(int[] nums, int k, int i) { int temp = nums[k]; nums[k] = nums[i]; nums[i] = temp; return nums; } }

 

 用arraylist的方法：

public class Solution { public List<List<Integer>> permute(int[] nums) { List<List<Integer>> res = new ArrayList<List<Integer>>(); Arrays.sort(nums); LinkedList<Integer> list = new LinkedList<Integer>(); for (int num : nums) list.add(num); perm(list, 0, res); return res; } private void perm(LinkedList<Integer> nums, int start, List<List<Integer>> res){ if (start == nums.size() - 1){ res.add(new LinkedList<Integer>(nums)); return; } for (int i = start; i < nums.size(); i++){ // if (i > start && nums.get(i) == nums.get(i - 1)) continue; nums.add(start, nums.get(i)); nums.remove(i + 1); perm(nums, start + 1, res); nums.add(i + 1, nums.get(start)); nums.remove(start); } } }

 

转载于:https://www.cnblogs.com/hygeia/p/5094347.html

相关资源：JAVA上百实例源码以及开源项目