力扣(LeetCode)47

小灰灰 2022-03-07 12:36 158阅读 0赞

题目地址：  
[https://leetcode-cn.com/probl...][https_leetcode-cn.com_probl...]  
题目描述：  
给定一个可包含重复数字的序列，返回所有不重复的全排列。

示例:

输入: \[1,1,2\]  
输出:  
\[  
\[1,1,2\],  
\[1,2,1\],  
\[2,1,1\]  
\]  
解答：  
这一题可以利用求下一个排列算法来求解，对原数组排序，然后加入一个结果，接着不断求下一个排列，直到没有下一个排列为止。而下一个排列的求解,可以参考[下一个排列][Link 1]

java ac代码:

class Solution {
        public List<List<Integer>> permuteUnique(int[] nums) {
            List<List<Integer>>ans = new ArrayList(1000);
            Arrays.sort(nums);
            List<Integer> temp = new ArrayList();
            for(int i = 0;i < nums.length;i++)
                temp.add(nums[i]);
            ans.add(temp);
            
            while(true)
            {
                temp = nextpermute(nums);
                if(temp.size() > 0)
                    ans.add(temp);
                else break;
            }
            return ans;
        }
        
        List<Integer> nextpermute(int[]nums)
        {
            List<Integer>ans = new ArrayList(nums.length);
            for(int i = 0;i < nums.length-1;i++)
                if(nums[i]<nums[i+1])
                {
                    int j = nums.length-1;
                    while(true)
                    {
                        if(nums[j-1] < nums[j])
                            break;
                        j--;
                    }
                    int k = nums.length-1;
                    while(true)
                    {
                        if(nums[k] > nums[j-1])
                        {
                            swap(nums,j-1,k);
                            int l = j,r = nums.length-1;
                            while(l < r)
                            {
                                swap(nums,l,r);
                                l++;
                                r--;
                            }
                            for(int q = 0;q < nums.length;q++)
                                ans.add(nums[q]);
                            break;
                        }
                        k--;
                    }
                    
                    
                    break;
                }
            return ans;
        }
        
        void swap(int[]nums,int i,int j)
        {
            int temp = nums[i];
            nums[i] = nums[j];
            nums[j] = temp;
        }
    }

[https_leetcode-cn.com_probl...]: https://leetcode-cn.com/problems/permutations-ii/
[Link 1]: https://segmentfault.com/a/1190000018255586