LeetCode : 46. Permutations 全排列

傷城~ 2021-06-24 16:11 395阅读 0赞

**试题**  
Given a collection of distinct integers, return all possible permutations.

Example:

Input: \[1,2,3\]  
Output:  
\[  
\[1,2,3\],  
\[1,3,2\],  
\[2,1,3\],  
\[2,3,1\],  
\[3,1,2\],  
\[3,2,1\]  
\]

**代码**  
把上次写的下一排列，调整一下。

class Solution {
        public List<List<Integer>> permute(int[] nums) {
            Arrays.sort(nums);
            List<List<Integer>> out = new ArrayList<List<Integer>>();
            
            ArrayList<Integer> tmp = new ArrayList<>();
            for(int n : nums) tmp.add(n);
            out.add(tmp);
            
            while(nextPermutation(nums)){
                // ArrayList<Integer> tmp = new ArrayList<Integer>(Arrays.asList(nums)); //错误写法，asList不支持int类型
                ArrayList<Integer> tmpb = new ArrayList<>();
                for(int n : nums) tmpb.add(n);
                out.add(tmpb);
            }
            return out;
        }
        
        public boolean nextPermutation(int[] nums) {
            if(nums==null || nums.length<=1) return false;
            int len = nums.length;
            
            int cur = len-1;
            while(cur-1>=0 && nums[cur-1]>=nums[cur]) cur--;
            if(cur==0){
                return false;
            }
            
            cur--;
            int lo = cur;
            while(cur+1<len && nums[cur+1]>nums[lo]) cur++;
            swap(nums, lo, cur);
            reverse(nums, lo+1, len-1);
            return true;
        }
        
        public void reverse(int[] nums, int left, int right){
            while(left<right){
                swap(nums, left, right);
                left++;
                right--;
            }
        }
        
        public void swap(int[] nums, int i, int j){
            int temp = nums[i];
            nums[i] = nums[j];
            nums[j] = temp;
        }
        
    }