算法leetcode｜47. 全排列 II（rust重拳出击）

文章目录

47. 全排列 II：

给定一个可包含重复数字的序列

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

分析：

• 面对这道算法题目，二当家的陷入了沉思。
• 要做全排列，回溯是大方向。
• 有重复的数字，又要不重复的排列，去重是必须的了。
• 要求是对排列去重，但是也可以理解为回溯时，跳过已经“尝试”过的数字。
• 如果数字很多，可以考虑计数排序法，这里顺序不重要，重要的是快速去重。
• 但是提示里说数字最多8个，那直接排序，同样顺序不重要，只是为了相同的数字挨在一起，每次回溯跳过相同数字即可。

题解：

rust

implSolution{pubfnpermute_unique(mut nums:Vec<i32>)->Vec<Vec<i32>>{fnbacktrack(nums:&Vec<i32>, ans:&mutVec<Vec<i32>>, vis:&mutVec<bool>, row:&mutVec<i32>){if row.len()== nums.len(){
                ans.push(row.clone());return;}
            nums.iter().enumerate().for_each(|(i, v)|{if!vis[i]&&(i ==0|| nums[i]!= nums[i -1]|| vis[i -1]){
                    row.push(nums[i]);
                    vis[i]=true;backtrack(nums, ans, vis, row);
                    row.pop();
                    vis[i]=false;}});}letmut ans =Vec::new();
        nums.sort();letmut vis =vec![false; nums.len()];letmut row =Vec::new();backtrack(&mut nums,&mut ans,&mut vis,&mut row);return ans;}}

go

funcpermuteUnique(nums []int)(ans [][]int){var backtrack func([]bool,[]int)
    backtrack =func(vis []bool, row []int){iflen(row)==len(nums){
            ans =append(ans,append([]int(nil), row...))return}for i, v :=range nums {if vis[i]|| i >0&&!vis[i-1]&& v == nums[i-1]{continue}
            row =append(row, v)
            vis[i]=truebacktrack(vis, row)
            row = row[:len(row)-1]
            vis[i]=false}}

    sort.Ints(nums)backtrack(make([]bool,len(nums)),[]int{})return}

c++

classSolution{private:voidbacktrack(vector<int>& nums, vector<vector<int>>& ans, vector<bool>& vis, vector<int>& row){if(row.size()== nums.size()){
            ans.emplace_back(row);return;}for(int i =0; i < nums.size();++i){if(vis[i]||(i >0&& nums[i]== nums[i -1]&&!vis[i -1])){continue;}
            row.emplace_back(nums[i]);
            vis[i]=true;backtrack(nums, ans, vis, row);
            row.pop_back();
            vis[i]=false;}}public:
    vector<vector<int>>permuteUnique(vector<int>& nums){
        vector<vector<int>> ans;
        vector<int> row;
        vector<bool>vis(nums.size(),false);sort(nums.begin(), nums.end());backtrack(nums, ans, vis, row);return ans;}};

c

intcmp(void* a,void* b){return*(int*)a -*(int*)b;}voidbacktrack(int* nums,int numSize,int** ans,int* ansSize, bool* vis,int* row,int idx){if(idx == numSize){int*tmp =malloc(sizeof(int)* numSize);memcpy(tmp, row,sizeof(int)* numSize);
        ans[(*ansSize)++]= tmp;return;}for(int i =0; i < numSize;++i){if(vis[i]||(i >0&& nums[i]== nums[i -1]&&!vis[i -1])){continue;}
        row[idx]= nums[i];
        vis[i]= true;backtrack(nums, numSize, ans, ansSize, vis, row, idx +1);
        vis[i]= false;}}/**
 * Return an array of arrays of size *returnSize.
 * The sizes of the arrays are returned as *returnColumnSizes array.
 * Note: Both returned array and *columnSizes array must be malloced, assume caller calls free().
 */int**permuteUnique(int* nums,int numsSize,int* returnSize,int** returnColumnSizes){int** ans =malloc(sizeof(int*)*2001);int* row =malloc(sizeof(int)* numsSize);
    bool* vis =malloc(sizeof(bool)* numsSize);memset(vis, false,sizeof(bool)* numsSize);qsort(nums, numsSize,sizeof(int), cmp);*returnSize =0;backtrack(nums, numsSize, ans, returnSize, vis, row,0);*returnColumnSizes =malloc(sizeof(int)*(*returnSize));for(int i =0; i <*returnSize; i++){(*returnColumnSizes)[i]= numsSize;}return ans;}

python

classSolution:defpermuteUnique(self, nums: List[int])-> List[List[int]]:defbacktrack(nums: List[int], ans: List[List[int]], vis: List[bool], row: List[int]):iflen(row)==len(nums):
                ans.append(row.copy())returnfor i inrange(len(nums)):ifnot vis[i]:if i >0and nums[i]== nums[i -1]andnot vis[i -1]:continue
                    row.append(nums[i])
                    vis[i]=True
                    backtrack(nums, ans, vis, row)
                    row.pop()
                    vis[i]=False

        nums.sort()
        ans =[]
        backtrack(nums, ans,[False]*len(nums),[])return ans

java

classSolution{publicList<List<Integer>>permuteUnique(int[] nums){List<List<Integer>> ans =newArrayList<>();Arrays.sort(nums);backtrack(nums, ans,newboolean[nums.length],newLinkedList<>());return ans;}privatevoidbacktrack(int[] nums,List<List<Integer>> ans,boolean[] vis,Deque<Integer> row){if(row.size()== nums.length){
            ans.add(newArrayList<>(row));return;}for(int i =0; i < nums.length;++i){if(vis[i]||(i >0&& nums[i]== nums[i -1]&&!vis[i -1])){continue;}
            row.push(nums[i]);
            vis[i]=true;backtrack(nums, ans, vis, row);
            row.pop();
            vis[i]=false;}}}

非常感谢你阅读本文~
欢迎【点赞】【收藏】【评论】~
放弃不难，但坚持一定很酷~
希望我们大家都能每天进步一点点~
本文由 二当家的白帽子：https://le-yi.blog.csdn.net/ 博客原创~