[NC]42. 有重复项数字的所有排列

🚩传送门：牛客题目

题目

给出一组可能包含重复项的数字，返回该组数字的所有排列。结果以字典序升序排列。
要求：空间复杂度 ，时间复杂度
示例1：

输入：[1,1,2] 返回值：[[1,1,2],[1,2,1],[2,1,1]]

示例2：

输入：[0,1] 返回值：[[0,1],[1,0]]

解题思路：nextPermutation

通过 nextPermutation 将所有字典排序序列列出来

复杂度分析

时间复杂度：

空间复杂度：

我的代码

public class Solution {
    public boolean nextPermutation(int[]nums){
        int i = nums.length - 2;
        //1. 找出 i<ii 的部分
        while (i >= 0 && nums[i] >= nums[i + 1]) {
            i--;
        }
        if (i < 0) {
            return false;
        }
        int j = nums.length - 1;
        //2. 找出 j>i 的部分
        while (j >= 0 && nums[i] >= nums[j]) {
            j--;
        }
        //3. 交换(i,j)
        swap(nums, i, j);
        //4. 反转 ii 之后元素
        reverse(nums, i + 1,nums.length-1);
        return true;
    }
    public ArrayList<ArrayList<Integer>> permuteUnique(int[] num) {
        //1. 先排序
        Arrays.sort(num);
        ArrayList<ArrayList<Integer>>res=new ArrayList<>();
        //2. 找字典排序
        do{
            ArrayList<Integer>list=new ArrayList<>();
            for(int e:num)list.add(e);
            res.add(list);
        }while(nextPermutation(num));
        //3. 返回结果集
        return res;
    }
}