题解 | #没有重复项数字的所有排列#

没有重复项数字的所有排列

http://www.nowcoder.com/practice/4bcf3081067a4d028f95acee3ddcd2b1

题解一:回溯
题解思路: 每次尝试选一个数,不满足条件就回溯
图示:
图片说明

 约束条件:数组不能重复使用.
 递归分析: cur==num.size 表示找到一个全排列
 递归过程: 如果该数字能添加,那么将vis置位1 ,表示该数字已经用了。
  回溯: 恢复状态
复杂度分析:
 时间复杂度: : 共有n!个叶节点,需要使用O(N)的时间复制到目标数组
 空间复杂度: :排列个数N!,每个排列占N
实现如下:

class Solution {
public:
    int vis[1001];
    vector<vector<int> >ans;
    void dfs(vector<int>& num,int cur,vector<int>&Permutation){
        if(cur==num.size()) {ans.emplace_back(Permutation);return;} //生成了一个排列
        for(int i = 0;i<num.size();i++){
            if(vis[i]!=1){  //没有使用过
                vis[i] = 1;
               Permutation.emplace_back(num[i]);
                dfs(num,cur+1,Permutation);
                //回溯
                vis[i] = 0;
               Permutation.pop_back();  
            }
        }
    }
    vector<vector<int> > permute(vector<int> &num) {
        vector<int> Permutation;
        dfs(num, 0,Permutation);
        return ans;
    }
};

题解二:位运算
题解思路:使用二进制位代替了标记数组
比如: 0001表示第一位使用了 0010 表示第二位使用了,0011表示第一位和第二位已经使用了。由于本题的数据弱,一个int数据可以标记完所有数,所以可以使用本方法。或者改用long long。
复杂度分析:
 时间复杂度:,同方法一
 空间复杂度:,同方法一
实现如下:

class Solution {
public:
    vector<int> tmp;
    vector<vector<int> >ans;
    vector<vector<int> > permute(vector<int> &num) {
      int len = num.size();
      Permutation(num,len,0);
      return ans;
    }
    void Permutation(vector<int>& num,int len,int vis){
        for(int i = 0;i<len;++i){
            int cur = 1<<i; //标识当前使用的第几位数
            if((cur&vis)==0){
                tmp.push_back(num[i]);
                Permutation(num,len,vis|cur); 
            }
        }
        if(tmp.size()==len) ans.push_back(tmp);
        tmp.pop_back(); // 回溯
        return;
    }
};
牛客网编程题题解 文章被收录于专栏

本专栏记录在牛客网上AC的每一题,写下题解。 未来2年完成2000编程题的题解。 2021.12.29更新,最进准备毕设,断更了,会尽快做完毕设,继续做这一件事情

全部评论

相关推荐

2 收藏 评论
分享
牛客网
牛客企业服务