LeetCode47——Permutations II

清疚 2022-08-09 12:41 257阅读 0赞

LeetCode47——Permutations II

含重复元素的全排列，仍然是套用了下一个全排列的方法。

跟上题一样，有时间补上递归解法。

代码：

class Solution {
    private:
    	void Swap(int &a, int &b)
    	{
    		int temp = a;
    		a = b;
    		b = temp;
    	}
    	bool Permutation(vector<int>&nums, int first, int last)
    	{
    		if (first == last)//长度为1
    			return false;
    		int i;
    		i = last;
    		while (1)
    		{
    			int ii = i;
    			--i;
    			//锁定两个相邻的元素
    			if (nums[i] < nums[ii])//前一个元素小于后一个元素
    			{
    				int j = last;
    				while (!(nums[i] < nums[j--]));//尾端往前找找到比nums[i]大的元素
    				Swap(nums[i], nums[j+1]);
    				reverse(nums.begin()+ii, nums.end());
    				return true;
    			}
    			if (i == first)
    			{
    				reverse(nums.begin(),nums.end());
    				return false;
    			}
    		}
    	}
    public:
        vector<vector<int>> permuteUnique(vector<int>& nums) {
           vector<vector<int>>result;
           sort(nums.begin(),nums.end());
           result.push_back(nums);
           while(Permutation(nums,0,nums.size()-1))
           {
               result.push_back(nums);
           }
          // result.push_back(nums);
           return result;
        }
    };

发表评论取消回复

表情：

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

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

相关阅读

相关 47. Permutations II(全排列）

给定一组可能包含重复项的数字，请返回所有可能的唯一排列。（不能有重复的）例：输入： \[1,1,2\] 输出： \[ \[1,1,2\], \[1,

墨蓝/ 2023年07月24日 02:52/ 0 赞/ 28 阅读

相关 LeetCode 47. Permutations II (Java版; Meidum)

[welcome to my blog][] LeetCode 47. Permutations II (Java版; Meidum) 题目描述 Gi

曾经终败给现在/ 2023年07月21日 11:27/ 0 赞/ 115 阅读

相关 LeetCode - Medium - 47. Permutations II

Topic Backtracking Description [https://leetcode.com/problems/permutations-ii/

喜欢ヅ旅行/ 2023年01月13日 10:25/ 0 赞/ 185 阅读

相关 LeetCode47——Permutations II

LeetCode47——Permutations II 含重复元素的全排列，仍然是套用了下一个全排列的方法。跟上题一样，有时间补上递归解法。代码： clas

清疚/ 2022年08月09日 12:41/ 0 赞/ 258 阅读

相关 Leetcode: Permutations II

题目： Given a collection of numbers that might contain duplicates, return all possible u

Bertha 。/ 2022年08月07日 15:59/ 0 赞/ 258 阅读

相关 Permutation II--LeetCode

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

痛定思痛。/ 2022年08月07日 11:46/ 0 赞/ 191 阅读

相关 leetcode 47. Permutations II 全排列问题（去掉重复元素）+递归

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

野性酷女/ 2022年06月09日 10:19/ 0 赞/ 346 阅读

相关 [Leetcode][python]Permutations II/全排列 II

题目大意求一组数的全排列（有重复数字），返回不重复的全排列解题思路详见上一题：[http://blog.csdn.net/qqxx6661/article/

朱雀/ 2022年06月07日 02:11/ 0 赞/ 314 阅读

相关 47. Permutations II

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

向右看齐/ 2022年03月07日 10:36/ 0 赞/ 278 阅读

相关 leetcode--Permutations II

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

Dear 丶/ 2021年10月25日 12:38/ 0 赞/ 399 阅读