leetcode47 全排列2

水深无声 2022-12-04 07:33 212阅读 0赞

leetcode47 全排列2

本题目可以采用深度优先搜索(递归)的方法进行探索来遍历所有的可能结果。即每次固定一个数字然后对剩下的数字进行下一步探索即可（此时先不考虑去重操作）。

接下来，我们将进行进行去重。不难发现，得到重复的原因无非就是我们在固定数字的时候出现了固定重复的数字。因此，我们可以使用map来进行哈希去重即可。如果即将固定的数字在之前已经出现过，我们可以直接跳过该数字的固定。

具体代码实现如下：

class Solution {
    
    public:
    
        vector<vector<int>> permuteUnique(vector<int>& nums) {
    
            sort(nums.begin(),nums.end());
    
            size=nums.size();
    
            permuteUnique(nums,0);
    
            return res;
    
        }
    
    private：
    
        void permuteUnique(vector<int> & nums ,int index){
    
            if(index==size-1) {
    
                res.push_back(nums);
    
                return;
    
            }
    
            //使用map进行去重
    
            unordered_map<int,bool> m;
    
            for(int i=index;i<size;i++){
    
                if(m.find(nums[i])!=m.end()) continue;
    
                m[nums[i]]=true;
    
                swap(nums[i],nums[index]);
    
                permuteUnique(nums,index+1);
    
                swap(nums[i],nums[index]);
    
            }
    
            return ;
    
        }
    
        vector<vector<int>> res;
    
        int size;
    
        //int num;
    
    };

发表评论取消回复

表情：

评论列表（有 0 条评论，212人围观）

还没有评论，来说两句吧...

相关阅读

相关 LeetCode-47. 全排列 II

目录题目思路回溯法拓展题目来源 [47. 全排列 II][47. _ II] 题目思路这道题目和46.全排

青旅半醒/ 2024年03月26日 02:25/ 0 赞/ 46 阅读

相关【LeetCode 47】全排列 II

题目描述给定一个可包含重复数字的序列，返回所有不重复的全排列。示例: 输入: [1,1,2] 输出: [ [1,1,2],

野性酷女/ 2022年12月06日 04:25/ 0 赞/ 168 阅读

相关 leetcode47 全排列2

leetcode47 全排列2 本题目可以采用深度优先搜索(递归)的方法进行探索来遍历所有的可能结果。即每次固定一个数字然后对剩下的数字进行下一步探索即可（此时先不考虑去重操

水深无声/ 2022年12月04日 07:33/ 0 赞/ 213 阅读

相关 leetcode 47全排列2 js

leetcode 47全排列2 给定一个可包含重复数字的序列 `nums` ，按任意顺序返回所有不重复的全排列。示例 1：输入：nums = [1,1,

忘是亡心i/ 2022年11月12日 08:16/ 0 赞/ 149 阅读

相关 LeetCode 47. 全排列 II

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ub

雨点打透心脏的1/2处/ 2022年11月03日 15:30/ 0 赞/ 165 阅读

相关 leetcode 47 全排列II

题目题目：[47. 全排列 II][47. _ II] 参考题解：[47.全排列 II-代码随想录][47._ II-] --------------------

我不是女神ヾ/ 2022年09月14日 09:12/ 0 赞/ 180 阅读

相关 LeetCode47. 全排列 II

给定一个可包含重复数字的序列，返回所有不重复的全排列。示例: 输入: [1,1,2] 输出: [ [1,1,2], [1,

Bertha 。/ 2022年05月14日 09:13/ 0 赞/ 209 阅读

相关【LeetCode】47. 全排列 II

题目链接：[https://leetcode-cn.com/problems/permutations-ii/description/][https_leetcode-cn.c

àì夳堔傛蜴生んèń/ 2022年05月03日 00:56/ 0 赞/ 196 阅读

相关 leetcode:47. 全排列 II

题目: 给定一个可包含重复数字的序列，返回所有不重复的全排列。示例: 输入: \[1,1,2\] 输出: \[ \[1,1,2\], \[1,2,1

超、凢脫俗/ 2022年04月11日 10:14/ 0 赞/ 211 阅读

相关 leetcode:47.全排列 II

题目描述：给定一个可包含重复数字的序列，返回所有不重复的全排列。示例：输入: [1,1,2] 输出: [ [1,1,2]

待我称王封你为后i/ 2022年02月01日 12:43/ 0 赞/ 202 阅读