NumsSort

发表于 更新于 分类于

题目描述[题目描述][https://www.acwing.com/problem/content/description/47/]

输入一组数字（可能包含重复数字），输出其所有的排列方式。

样例

1
2
3
4
5
6
7
8
9
10
11
输入：[1,2,3]

输出：
      [
        [1,2,3],
        [1,3,2],
        [2,1,3],
        [2,3,1],
        [3,1,2],
        [3,2,1]
      ]

算法描述

定义一个标记数组，每选择一个元素，标记位取反一次。处理相同元素的问题，第一步将数组排序，依次遍历，如果当前元素被选择了跳过，如果当前元素的前一个元素等于本身，并且前面的元素没有被选择，跳过当前元素，直到遍历完成

C++代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution {
public:

    vector<vector<int>> ans;
    vector<int> vec;

    void dfs(vector<int>& nums,int x,int state,int start){
        if(x==nums.size()){
            ans.push_back(vec);
            return;
        }
        if(!x||nums[x]!=nums[x-1])start=0;
        for(int i=start;i<nums.size();i++){
            if((state>>i)&1){
                vec[x]=nums[i];
                dfs(nums,x+1,state+(1<<i),i+1);
            }
        }
    }
    
    vector<vector<int>> permutation(vector<int>& nums) {
        if(nums.size()==0)return ans;
        sort(nums.begin(),nums.end());
        vec.resize(nums.size());
        dfs(nums,0,0,0);
        return ans;
    }
};

Java代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution {

    List<List<Integer>> ans =  new ArrayList<>();
    List<Integer> res = new ArrayList<>();
    boolean[] falg;
    
    public void dfs(int[] nums){
        if(res.size()==nums.length){
            ans.add(new ArrayList<>(res));
            return;
        }
        for(int i = 0;i<nums.length;i++){
            if(falg[i]||i>0&&nums[i-1]==nums[i]&&falg[i-1]==false)continue;
            falg[i]=true;
            res.add(nums[i]);
            dfs(nums);
            res.remove(res.size()-1);
            falg[i]=false;
        }
        return ;
    }
    
    public List<List<Integer>> permutation(int[] nums) {
        Arrays.sort(nums);
        falg = new boolean[nums.length];
        dfs(nums);
        return ans;
    }
}