首页 > 编程语言 >(算法)全排列Ⅱ————<递归>

(算法)全排列Ⅱ————<递归>

时间:2024-07-30 15:53:55浏览次数:13  
标签:排列 递归 nums 元素 算法 vector path check

1. 题⽬链接:47.全排列II 

2. 题⽬描述:

3. 解法:

算法思路:

因为题⽬不要求返回的排列顺序,因此我们可以对初始状态排序,将所有相同的元素放在各⾃相邻的 位置,⽅便之后操作。因为重复元素的存在,我们在选择元素进⾏全排列时,可能会存在重复排列, 例如:[1,2,1],所有的下标排列为:

 

 按照以上下标进⾏排列的结果为:

 

可以看到,有效排列只有三种[1,1,2],[1,2,1],[2,1,1],其中每个排列都出现两次。因此,我们需 要对相同元素定义⼀种规则,使得其组成的排列不会形成重复的情况:

1. 我们可以将相同的元素按照排序后的下标顺序出现在排列中,通俗来讲,若元素s出现x次,则排 序后的第2个元素s⼀定出现在第1个元素s后⾯,排序后的第3个元素s⼀定出现在第2个元素s后⾯,以此类推,此时的全排列⼀定不会出现重复结果。

2. 例如:a1=1,a2=1,a3=2,排列结果为[1,1,2]的情况只有⼀次,即a1在a2前⾯,因为a2不会 出现在a1前⾯从⽽避免了重复排列。

3. 我们在每⼀个位置上考虑所有的可能情况并且不出现重复;

4. *注意*:若当前元素的前⼀个相同元素未出现在当前状态中,则当前元素也不能直接放⼊当前状态 的数组,此做法可以保证相同元素的排列顺序与排序后的相同元素的顺序相同,即避免了重复排列 出现。

5. 通过深度优先搜索的⽅式,不断地枚举每个数在当前位置的可能性,并在递归结束时回溯到上⼀个 状态,直到枚举完所有可能性,得到正确的结果。

递归函数设计:void backtrack(vector& nums, int idx) 

参数:idx(当前需要填⼊的位置); 

返回值:⽆;

函数作⽤:查找所有合理的排列并存储在答案列表中。  

递归流程如下:

1. 定义⼀个⼆维数组ans⽤来存放所有可能的排列,⼀个⼀维数组perm⽤来存放每个状态的排列, ⼀个⼀维数组visited标记元素,然后从第⼀个位置开始进⾏递归;

2. 在每个递归的状态中,我们维护⼀个步数idx,表⽰当前已经处理了⼏个数字;

3. 递归结束条件:当idx等于nums数组的⻓度时,说明我们已经处理完了所有数字,将当前数组存 ⼊结果中;

4. 在每个递归状态中,枚举所有下标i,若这个下标未被标记,并且在它之前的相同元素被标记过, 则使⽤nums数组中当前下标的元素:

        a. 将visited[i]标记为1; 

        b. 将nums[i]添加⾄perm数组末尾;

        c. 对第step+1个位置进⾏递归;

        d. 将visited[i]重新赋值为0,并删除perm末尾元素表⽰回溯;

5. 最后,返回ans。

 C++算法代码:

class Solution 
{
public:
    vector<vector<int>>answer;
    vector<int>temp;    //单个序列
    int key[9]={0}; //状态数组
    void dfs(vector<int>& nums)
    {
        //出口
        if(temp.size()==nums.size())
        {
            //查重
            if (find(answer.begin(),answer.end(),temp)==answer.end())
            {
                answer.push_back(temp);
            }
            return ;
        }
        for(int i=0;i<nums.size();i++)
        {
            if(!key[i])
            {
                //更新状态数组
                key[i]=1;
                temp.push_back(nums[i]);
                dfs(nums);
                //恢复现场
                temp.pop_back();
                key[i]=0;
            }
        }
    }
    vector<vector<int>> permuteUnique(vector<int>& nums) 
    {
        dfs(nums);
        return answer;
    }
};
class Solution
{
	vector<int> path;
	vector<vector<int>> ret;
	bool check[9];
public:
	vector<vector<int>> permuteUnique(vector<int>& nums)
	{
		sort(nums.begin(), nums.end());
		dfs(nums, 0);
		return ret;
	}
	void dfs(vector<int>& nums, int pos)
	{
		if (pos == nums.size())
		{
			ret.push_back(path);
			return;
		}
		for (int i = 0; i < nums.size(); i++)
		{
			// 剪枝 
			if (check[i] == false && (i == 0 || nums[i] != nums[i - 1] ||
				check[i - 1] != false))
			{
				path.push_back(nums[i]);
				check[i] = true;
				dfs(nums, pos + 1);
				path.pop_back(); // 恢复现场 
				check[i] = false;
			}

		}
	}
};

Java算法代码:

class Solution
{
	List<Integer> path;
	List<List<Integer>> ret;
	boolean[] check;
	public List<List<Integer>> permuteUnique(int[] nums)
	{
		path = new ArrayList<>();
		ret = new ArrayList<>();
		check = new boolean[nums.length];
		Arrays.sort(nums);
		dfs(nums, 0);
		return ret;
	}
	public void dfs(int[] nums, int pos)
	{
		if (pos == nums.length)
		{
			ret.add(new ArrayList<>(path));
			return;
		}
		for (int i = 0; i < nums.length; i++)
		{
			// 剪枝 
			if (check[i] == false && (i == 0 || nums[i] != nums[i - 1] ||
				check[i - 1] != false))
			{
				path.add(nums[i]);
				check[i] = true;
				dfs(nums, pos + 1);
				// 回溯 -> 恢复现场 
				path.remove(path.size() - 1);
				check[i] = false;
			}
		}
	}
}

标签:排列,递归,nums,元素,算法,vector,path,check
From: https://blog.csdn.net/2301_79580018/article/details/140798631

相关文章

  • 比传统PID算法更容易实现和调试的增量调速法
    当你接到一个控制任务,比如需要控制电机的转速,并支持动态快速调整转速,电机的转速可以实时获取。然后开始网上一顿搜索,搜索结果大致如下所述。在自动控制领域中,PID控制算法是一种非常常见且有效的控制算法,用于实现闭环控制系统中的精确控制。PID控制器由三个组成部分构成:比例......
  • 找到排列中的 1
    题目大意评测机保存一个秘密的\(1\simn\)的排列\(a\),允许你进行两种询问:询问\(i,j,k\),评测机告诉你是否有\(k\mid(a_i-a_j)\)询问\(i,j\),评测机告诉你是否有\(a_i<a_j\)其中,询问\(2\)最多进行一次,询问\(1\)可以进行任意次,但是不能超时。你需要确定\(1\)在排......
  • Day 28 贪心算法 Part02
    55.跳跃游戏这道题我是从后往前做的,但由于用了递归,速度会慢一些,但整体时间复杂度也是O(N)。我的思路其实就是找到最后一个可以到达目标位置处的下标,如果不存在这样的位置,就说明最后一个位置不可达。假设找到了,我们就需要去判断找到的这个位置是否可达,此时它的可达性与最后一个......
  • C语言 —— 函数递归
    目录1.什么是递归2.递归的思想3.递归的限制条件4.递归的举例4.1求n的阶乘4.2分析和代码实现4.3画图推演5.递归与迭代1.什么是递归递归是学习C语言函数绕不开的话题,那什么是递归呢?递归其实是一种解决问题的方法,在C语言中,递归就是函数自己调用自己。#inc......
  • 区块链共识协议算法
    一、常见共识协议算法1.ByzantineFaultTolerance(BFT)BFT是一种容错算法,旨在在系统中存在一部分恶意或故障节点的情况下,仍然能够达到一致性。特点:容忍拜占庭故障,即能够处理部分节点不可靠或恶意的情况。通常适用于许可链(私有链或联盟链)。应用:HyperledgerFabri......
  • python之代码简化式(列表、字典生成式,递归函数,迭代器(iter)和生成器(yield)、匿名函数(
    文章目录前言1、列表、字典生成式2、递归函数2.1python中代码的递归深度(扩展)3、拓展:迭代器和生成器3.1迭代器(iter)3.2生成器(yield)4、匿名函数(lambda)4.1map函数4.2reduce函数(较少使用)4.3filter函数前言本文主要讲解一些简化代码格式的一些方法,方便大家更好的......
  • Day14 二叉树Part2 递归的应用(二叉树相关)
    任务226.翻转二叉树给你一棵二叉树的根节点root,翻转这棵二叉树,并返回其根节点。思路逻辑上,我们知道用递归遍历一棵树,一定会遍历每个节点。因此在遍历的过程中处理即可。考虑递归基,即当节点为空时直接返回。考虑单层递归,为了反转二叉树,如何处理当前节点呢?即如何反转以当......
  • 代码随想录算法训练营第28天 | 贪心进阶
    2024年7月30日题122.买卖股票的最佳时机II上涨就买,下跌就不买。classSolution{publicintmaxProfit(int[]prices){intsum=0;for(inti=1;i<prices.length;i++){sum+=prices[i]-prices[i-1]>0?prices[i]-prices[i-1]:0;......
  • 代码随想录算法训练营第27天 | 初入贪心
    2024年7月29日题455.分发饼干先排序,然后依次分发即可。classSolution{publicintfindContentChildren(int[]g,int[]s){//对于每个孩子胃口,从小到大分配,且给尽可能少的饼干Arrays.sort(g);Arrays.sort(s);intcnt=0;......
  • opencv 目标检测之canny算法
    cannycanny的目标有3个1.低错误率检测出的边缘都是真正的边缘2.定位良好边缘上的像素点与真正的边缘上的像素点距离应该最小3.最小响应边缘只能标识一次,噪声不应该标注为边缘canny分几步1.滤掉噪声比如高斯滤波2.计算梯度比如用索贝尔算子算出梯度3.非极大值......