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

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

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更新,最进准备毕设,断更了,会尽快做完毕设,继续做这一件事情

注意!此信息未认证,请谨慎判断信息的真实性!

全部评论
空

相关内容推荐

头像
点赞 评论 收藏
转发
头像 头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像 头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
2022-12-22 16:33
重庆工商大学_2024
点赞 评论 收藏
转发
头像
2022-12-23 17:45
武汉商学院_2023
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
点赞 收藏 评论
分享

全站热榜

正在热议