当前位置: 首页 > news >正文

[LeetCode]—Permutations II 求全排列(有重复值)

Permutations II

 

Given a collection of numbers that might contain duplicates, return all possible unique permutations.

For example,
[1,1,2] have the following unique permutations:
[1,1,2][1,2,1], and [2,1,1].

分析:

         本题在[LeetCode]—Permutations 求全排列 基础上,出现了重复值元素。

         方法一:使用STL next_permutions方法。个人实现版见:[LeetCode]—Next Permutation (全排列字典序)

         方法二:依然采用DFS深搜的办法,不过怎么避免重复就是关键问题了。

         其实,如果能够保证重复元素的使用先后顺序,就不会出现重复。即当前元素如果有重复,必须等到前面重复元素都被使用了,自己才能使用。

        例如:1(1),1(2), 2  括号中标示的是出现的次序。

        排列:1(1),1(2),2

                    1(1),2,1(2)

                    1(2),1(1),2    

                    1(2),2,1(2)    X                 

                    2,1(1),1(2)

                    2,1(2),1(1)    X   

    所以,重复元素,保证出现的次序是关键。

代码只需要在[LeetCode]—Permutations 求全排列 基础上多增加一个判断即可。增加28-34行

class Solution {
public:
    vector<vector<int> > permuteUnique(vector<int> &num) {
        vector<vector<int> > res;
        vector<int> cur;
        int count;
        int n=num.size();
        if(n<=1){
            res.push_back(num);
            return res;
        }
        sort(num.begin(),num.end());
        int *bit=new int[n];
        memset(bit,0,sizeof(int)*n);
        
        DFS(res,cur,num,0,bit);
        return  res;
    }
private:
   void DFS(vector<vector<int> > &res,vector<int> &cur,vector<int> &num,int count,int *bit){
       int n=num.size();
       if(count==n){
            res.push_back(cur);
            return;
       }
       for(int i=0;i<n;i++){
          if(!bit[i]){
             int j=i;
             while(num[--j]==num[i]){
                if(bit[j]==0){   //表示i之前还有未被使用相同元素,出现了重复元素不按序使用的情况
                    break;
                }
             }
             if(num[j]==num[i])continue;   //表示存在重复元素乱序使用;中断该种情况
             cur.push_back(num[i]);
             bit[i]=1;
             DFS(res,cur,num,count+1,bit);
             bit[i]=0;
             cur.pop_back();
          }
       }
    }
};


相关文章:

  • 动态装卸DLL示例-匪徒和
  • 一个困扰我一个多星期的Nebula3的BUG
  • [Python]—Linux Server 系统监控程序
  • .NET 4.0中使用内存映射文件实现进程通讯
  • 中国移动短信指令大全
  • SQLServer中的循环批处理
  • IT市场10大趋势!
  • 关于Oracel 10g http://ip:1158/em 的问题
  • 18句话入门SQLServer XML
  • 移动商务潜力无穷
  • 一道可以成为.NET面试“必杀题”的“简单问题”
  • Linux 简单的网络配置练习一
  • 解决Ubuntu 9.04 耳机有声音但外放无声问题
  • IPv4和IPv6比特转发率和包转发率的关系
  • [LeetCode]-Pascal's Triangle III 杨辉三角问题
  • 【刷算法】从上往下打印二叉树
  • 【跃迁之路】【477天】刻意练习系列236(2018.05.28)
  • 10个确保微服务与容器安全的最佳实践
  • CSS 提示工具(Tooltip)
  • Effective Java 笔记(一)
  • Koa2 之文件上传下载
  • node.js
  • PHP 使用 Swoole - TaskWorker 实现异步操作 Mysql
  • Vue.js 移动端适配之 vw 解决方案
  • Vue学习第二天
  • 程序员该如何有效的找工作?
  • 构建工具 - 收藏集 - 掘金
  • 机器学习 vs. 深度学习
  • 微服务框架lagom
  • 异步
  • 用Visual Studio开发以太坊智能合约
  • 中文输入法与React文本输入框的问题与解决方案
  • ​【C语言】长篇详解,字符系列篇3-----strstr,strtok,strerror字符串函数的使用【图文详解​】
  • ​一、什么是射频识别?二、射频识别系统组成及工作原理三、射频识别系统分类四、RFID与物联网​
  • # Java NIO(一)FileChannel
  • ###C语言程序设计-----C语言学习(3)#
  • #Lua:Lua调用C++生成的DLL库
  • #pragma once
  • #单片机(TB6600驱动42步进电机)
  • (14)目标检测_SSD训练代码基于pytorch搭建代码
  • (附源码)springboot 房产中介系统 毕业设计 312341
  • (三)Hyperledger Fabric 1.1安装部署-chaincode测试
  • (转)jQuery 基础
  • (转)Linux整合apache和tomcat构建Web服务器
  • (转)VC++中ondraw在什么时候调用的
  • (轉貼) 資訊相關科系畢業的學生,未來會是什麼樣子?(Misc)
  • (最完美)小米手机6X的Usb调试模式在哪里打开的流程
  • .bat文件调用java类的main方法
  • .mat 文件的加载与创建 矩阵变图像? ∈ Matlab 使用笔记
  • .NET Remoting Basic(10)-创建不同宿主的客户端与服务器端
  • .net Stream篇(六)
  • .NET框架类在ASP.NET中的使用(2) ——QA
  • .NET面试题(二)
  • .net中应用SQL缓存(实例使用)
  • .sh