0%

[0047] 全排列 II

发表于 更新于 分类于 ， 本文字数： 2.3k 阅读时长 ≈ 2 分钟
...

[0047] 全排列 II

题目描述

给定一个可包含重复数字的序列，返回所有不重复的全排列。

示例:

输入: [1,1,2]
输出:
[
  [1,1,2],
  [1,2,1],
  [2,1,1]
]

Related Topics
  • 回溯算法

    • 题目解析

    • 回溯法解决此题
    • 注意去重优化

    不确定性

    • 初始数组大小

    方法一：模拟选择法

    分析

    • 此题与全排列1很像，原来的数字是不重复的，现在的数字可以重复，所以要加上去重逻辑

    思路

    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
    30
    31
    32
    33
    34
    35
    permutation(set, selected) {
      if len(set)==0 { res.add(selected) return} // 所有数字都选择完毕，加入一个可行解
      for n in set {
        selected.add(n)
        set.remove(n) 
        permutation(set, selected)
       
        set.add(n)
        selected.remove(n)
      }
    }

    按照上述算法
    给出用例 [1,1,2]
    输出结果是 [1,1,2], [1,2,1],[1,1,2],[1,2,1], [2,1,1],[2,1,1] 可以看出有重复项。
    出现重复的关键是在同一个位置同样的数字被选择了多次。比如[1,1,2], [1,2,1],[1,1,2],[1,2,1]是因为在第1位1被重复使用。
    所以在选择数字时要判断这个数字在这个位置之前是不是选择过数值相等的数字了。
    方法如下：
    先对待选集合进行排序，在选择时判断一下之前选择的数字如果未被选择且与当前选择的相等，则说明重复选择了。

    优化后的思路
    set 要先排序
    permutationUnique(dep, set, selected) {
      if len(set)==dep { res.add(selected) return} // 所有数字都选择完毕，加入一个可行解
      for (i=0;i<len(set);i++) {
      	if (vis[i]) continue;
      	// 判断是不是选择过, i>0 是边界条件，否则i-1<0 程序出错
      	if (i>0 && !vis[i-1] && set[i]==set[i-1])continue;
      	vis[i]=true
        selected.add(set[i])
        permutationUnique(dep+1, set, selected)
        selected.remove(set[i])
        vis[i]=false
      }
    }

    注意

    • 终止条件判断
    • 结果去重

    知识点

    • dfs
    • 模拟排列选择

    复杂度

    • 空间复杂度O(n)
    • 时间复杂度O(n!)

    代码

    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
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    class Solution {
    private:
        vector<bool> vis;
        vector<vector<int> > res;
        void dfs(int dep, vector<int>& nums, vector<int> &select)
        {
            if (dep == nums.size())
            {
                res.push_back(select);
                return;
            }

            for(int i=0;i<nums.size();++i)
            {
                if (vis[i]) continue;
                if (i>0 && !vis[i-1] && nums[i]==nums[i-1])continue;

                vis[i]=true;

                select.push_back(nums[i]);

                dfs(dep+1, nums, select);
                select.pop_back();

                vis[i]=false;
            }
        }

    public:
        vector<vector<int>> permuteUnique(vector<int>& nums) {
            sort(nums.begin(), nums.end());
            vector<int> selected;
            int n = nums.size();
            vis.assign(n, false);
            res.clear();
            dfs(0, nums, selected);

            return res;
        }
    };
    /*
    [1,2,3]
    [1,2,1]
    [1]
    []
     */

    void outVector(vector<int> line)
    {
        for(auto n:line)
        {
            printf("%d ", n);
        }
        cout<<"-"<<endl;
    }

    相关题目

    相关文章