• 力扣每日一题47:全排列 ||


    题目描述:

    给定一个可包含重复数字的序列 nums ,按任意顺序 返回所有不重复的全排列。

    示例 1:

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

    示例 2:

    输入:nums = [1,2,3]
    输出:[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
    

    提示:

    • 1 <= nums.length <= 8
    • -10 <= nums[i] <= 10

    通过次数

    496.8K

    提交次数

    757.3K

    通过率

    65.6%

    思路和题解:

    这题和第46题全排列的进阶,序列中包含了重复的数字,要求我们返回不重复的序列。我们还是用回溯和思路来做。

    我们可以看作是有n个空格,我们要从左往右依次填入题目给定的n个数。我们可以用回溯的方法,依次判断每个位置能填哪些数字,当第n个位置填好后,我们就将当前数组放入答案数组中,递归结束。用一个visited数组时刻标记原始数组的对应位置被选的状态,这样可以避免相同位置的数重复使用。

    但是到这里并没有满足题目“全排列不重复”的要求,因为题目给定的序列不同位置的数可能想等,当不同位置的两个相同的数交换位置时会重复。就拿样例1来说,原数组[1,1,2],第一个1填进第一个空格后,第二个1也能填进第一个空格,这样就重复了。而我们上面做的只保证了第一个1不重复填入第一个空格。所以我们需要处理这个情况。

    要解决上面的问题我们需要保证,在填入某个空格(假设是第index个)的时候,我们要保证重复的数字只会被填入这个空格一次即可。我们先将原数组排序,在排好后,相同的数字都相邻。按照原来的步骤走,如果选择要填的数字没有相同的数那就放心地填进去;如果有相同的数字,为了满足值相等位置不相等的数在某个位置只填入一次,我们只能填入重复集合中“从左到右的第一个未被填过的数”,即加一个判断条件if (i > 0 && nums[i] == nums[i - 1] && !vis[i - 1]) { continue; }

    代码:

    一、回溯

    1. lass Solution {
    2. public:
    3. vector<int> visited;
    4. void dfs(vectorint>> &ans,vector<int> nums,vector<int> &perm,int depth,int n)
    5. {
    6. if(depth==n)
    7. {
    8. ans.emplace_back(perm);
    9. return;
    10. }
    11. for(int i=0;i
    12. {
    13. //这个位置的数已经填过 或者是 这个位置的前面有相等的数没填过
    14. if(visited[i]==1||(i>0&&nums[i]==nums[i-1]&&visited[i-1]==0))
    15. continue;
    16. //入栈,已选
    17. perm.emplace_back(nums[i]);
    18. visited[i]=1;
    19. //下一层
    20. dfs(ans,nums,perm,depth+1,n);
    21. //出栈,未选
    22. visited[i]=0;
    23. perm.pop_back();
    24. }
    25. }
    26. vectorint>> permuteUnique(vector<int>& nums) {
    27. sort(nums.begin(),nums.end());
    28. vectorint>> ans;
    29. vector<int> perm;
    30. visited.resize(nums.size());
    31. dfs(ans,nums,perm,0,nums.size());
    32. return ans;
    33. }
    34. };

    二、库函数:

    1. class Solution {
    2. public:
    3. vectorint>> permuteUnique(vector<int>& nums) {
    4. vectorint>> ans;
    5. sort(nums.begin(),nums.end());
    6. do{
    7. ans.emplace_back(nums);
    8. }while(next_permutation(nums.begin(),nums.end()));
    9. return ans;
    10. }
    11. };

  • 相关阅读:
    nlp小模型也可在控制和被控制结果的数据集(题库)上表现出智能
    uniapp——授权报错,选择合适的基础库
    AMRT3D数字孪生引擎详解
    Welcome to YARP - 4.限流 (Rate Limiting)
    元组高级用法
    java spring cloud 企业工程管理系统源码+二次开发+定制化服务
    区域人员超限AI算法的介绍及TSINGSEE视频智能分析技术的行业应用
    Java面试问题记录
    DC-3靶场搭建及渗透实战详细过程(DC靶场系列)
    git 将本地已有的一个项目上传到新建的git仓库的方法
  • 原文地址:https://blog.csdn.net/m0_73441691/article/details/133918230