• 首页

  • 文章归档

  • 文章分类

  • 日志

  • 图库

  • 友链

  • 留言板

  • 关于我
H i , m e g u m i
H i , m e g u m i

无名高

获取中...

09
18
算法题

LeetCode 47.全排列 II

发表于 2020-09-18 • leetcode 回溯 • 被 61 人看爆

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

示例:

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

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/permutations-ii
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。


思路:
这道题的关键在给定的序列可以包含重复的数字,不注意这一点可能会求得大量重复的全排列:重复数字填入顺序不同得到的排列是相同的全排列,不是不同的全排列。

eg:上面示例中有两个1,一个2,为了区分两个1 我们记作输入[1(1), 1(2), 2]
排列 [1(1), 1(2), 2]和排列[1(2), 1(1), 2]实际上是相同的排列
为了区分这类重复的全排列,我们固定重复数字的填入顺序:

  • 首先对输入序列排序,使相同的数字在序列中连续
  • 固定重复数字的填入顺序,即1(1)在所有1中一定是最先填入全排列中的数字,1(2)一定是所有1中第二排入全排列中的数字,依次类推...
  • 要想达到这一点:我们首先用一个数组visit[]表示第i个位置的数字是否填入了全排列中,其次设定条件,只有当重复数字的前一个数字填入了排列中,这个数字才可以填入全排列。假定当前判断是否要填入的数字为nums[i],只有当visit[i-1]==true && nums[i] == nums[i-1]时,重复数字才可以填入,也就是下面代码中visit[i-1]==false && nums[i] == nums[i-1]时,跳过当前重复数字nums[i],不允许填入

下面给出代码:

class Solution {
private:
    vector<bool> visit;
    vector<vector<int> > ans;
public:
    /**
     给定一个可包含重复数字的序列,返回所有不重复的全排列
     **/
    vector<vector<int>> permuteUnique(vector<int>& nums) {
        visit.resize(nums.size());
        sort(nums.begin(), nums.end());
        vector<int> tmp;
        getNextNum(nums, tmp, 0);
        return ans;
    }
    
    /**
     index 表示将要填的位置 从0~size-1的位置
     **/
    void getNextNum(vector<int>& nums, vector<int>& temp, int index){
        if (index == nums.size()) {// 填完了所有位置,获得一个全排列
            ans.push_back(temp);
//            cout << "获得一个全排列" << endl;
            return;
        }
        
        // index < n 还需要向当前index位置填入一个数字
        for (int i = 0; i < nums.size(); ++i) {
            // 如果nums[i] 填过了 或者 nums[i]不是当前连续重复数字的第一个位置
            if (visit[i] || (i > 0 && !visit[i-1] && nums[i] == nums[i-1] )) {
                continue;
            }
            // 填入当前nums[i]
//            cout << "填入数字" << nums[i] << endl;
            visit[i] = true;
            temp.push_back(nums[i]);
            // 获取下一个位置的数字
            getNextNum(nums, temp, index+1);
            temp.pop_back();
            visit[i] = false;
        }
    }
};
分享到:
LeetCode 404. 左叶子之和
LeetCode 685. 冗余连接 II
  • 文章目录
  • 站点概览
无名高

帅哥无名高

我们是如何走到这一步

Github QQ Email RSS
看爆 Top5
  • SpringBoot学习笔记 411次看爆
  • JDBC核心技术笔记 335次看爆
  • SpringMVC学习笔记 274次看爆
  • 解决在IDEA编写Java代码时,向数据库中插入中文字符后显示?乱码问题 267次看爆
  • Linux安装zookeeper 238次看爆
粤公网安备 44030702003128号
本站总访问量次 本站访客数人次

Copyright © 2021 无名高 · 黔ICP备20006240号

Proudly published with Halo · Theme by fyang · 站点地图