47. 全排列 II

系统管理员 2024-03-31 14:52 90阅读 0赞

> **关上过去和未来的铁门，活在“今天”这个舱室中。**——《人性的优点》

### 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

#### 思路：（回溯） ####

此题是 [46. 全排列][46.] 的进阶

*  但是这道题有了一点改变，那么就是列表里面有重复数字，全排列的结果，相同答案只算一种，那么我们就要考虑重复。
 *  当然因为题目没有说该队列有序，所以要先排序。

判断的时候加上：

if(i > 0 && nums[i] == nums[i-1] && hasVisited[i-1] == false) {
    	continue;
    }

其中最为关键的是 hasVisited\[i-1\] == false ，用来去重，就是**限制一下两个相邻的重复的访问顺序**

##### 举个栗子 ： #####

对于两个相同的数 1 1 ，我们将其命名为 a b，a 表示第一个 1 ，b 表示第二个 1

*  如果不去重得的话，会有两种重复排列 a b，b a ，我们只需取其中任意一种排列即可；
 *  为了达到目的，限制一下 a ，b 的访问顺序即可；
 *  比如 我们只取 a b 这个排列的话，只有当 nums\[i - 1\] 访问后，我们才去访问 nums\[i\] ，
 *  也就是说 如果 hasVisited\[i-1\] == false 的话， 则 continue 跳过。

##### 举另个栗子 ： #####

去重最为关键的代码为：

if(i > 0 && nums[i] == nums[i-1] && hasVisited[i-1] == false) {
    	continue;
    }

**但如果改成** hasVisited\[i-1\] == true ,**也是正确的**， 去重代码如下：

if(i > 0 && nums[i] == nums[i-1] && hasVisited[i-1] == true) {
    	continue;
    }

这是为什么呢？

*  hasVisited\[i-1\] == false ，是对**树层**中前一位去重；
 *  hasVisited\[i-1\] == true ，是对**树枝**前一位去重；

（借用一下别人的图进行理解）：

如果 是三个相同的数 1 1 1

**树层**上去重（hasVisited\[i-1\] == false），树形结构如下：  
![在这里插入图片描述][19f41f7b3b844e5496271b541efa4294.png]  
**树枝**上去重（hasVisited\[i-1\] == true），树形结构如下：  
![在这里插入图片描述][fd582a9d0edb49fab277b64241f4da88.png]  
观察上图可以得出：

*  树层上对前一位去重非常彻底，效率很高；
 *  树枝上对前一位去重虽然最后可以得到答案，但是做了很多无用搜索。

#### 代码：（Java） ####

import java.util.ArrayList;
    import java.util.List;
    
    public class all_permute {
        
    
    	public static void main(String[] args) {
        
    		// TODO 自动生成的方法存根
    		int [] nums = {
        1, 1, 2};
    		System.out.println(permuteUnique(nums));
    	}
    	public static List<List<Integer>> permuteUnique(int[] nums) {
        
    		List<List<Integer>> permutes = new ArrayList<>();
    		List<Integer> permute = new ArrayList<>();
    		if(nums == null || nums.length == 0) {
        
    			return permutes;
    		}
    		int flag = 0;//标记
    		for(int i = 1; i < nums.length ; i++) {
        //冒泡排序
    			for(int j = 0; j < nums.length - i; j++) {
        
    				if(nums[j] > nums[j+1]) {
        
    					int temp = nums[j];
    					nums[j] = nums[j+1];
    					nums[j+1] = temp;
    					flag++;
    				}
    			}
    			if(flag == 0)
    				break;
    		}
    		boolean [] hasVisited = new boolean[nums.length];
    		backTracking(nums, hasVisited, permute, permutes);
    		return permutes;
    	}
    	private static void backTracking(int[] nums, boolean[] hasVisited, List<Integer> permute, List<List<Integer>> permutes) {
        
    		// TODO 自动生成的方法存根
    		if(permute.size() == hasVisited.length) {
        
    			permutes.add(new ArrayList<>(permute));
    			return;
    		}
    		for(int i = 0; i < nums.length; i++) {
        
    			if(hasVisited[i]) {
        
    				continue;
    			}
    			if(i > 0 && nums[i] == nums[i-1] && hasVisited[i-1] == false) {
        
    				continue;
    			}
    			hasVisited[i] = true;
    			permute.add(nums[i]);
    			backTracking(nums, hasVisited, permute, permutes);
    			permute.remove(permute.size() - 1);
    			hasVisited[i] = false;
    		}
    	}
    }

##### 运行结果： #####

![在这里插入图片描述][70ba4f24495546c9a9671aa977c64a4c.png]

##### 复杂度分析： #####

*  时间复杂度： O ( n × n ! ) O(n×n!) O(n×n!)，其中 n 为序列的长度。
    
     *  算法的复杂度首先受 backTracking 的调用次数制约，backTracking 的调用次数为 ∑ k = 1 n P ( n , k ) \\sum\_\{k=1\}^\{n\} P(n, k) ∑k=1nP(n,k)次，其中  P ( n , k ) = n ! ( n − k ) ! = n ( n − 1 ) … ( n − k + 1 ) P(n, k)=\\frac\{n !\}\{(n-k) !\}=n(n-1) \\ldots(n-k+1) P(n,k)=(n−k)!n!=n(n−1)…(n−k\+1)，该式被称作 [n 的 k - 排列，或者部分排列][n _ k -]。
     *  而  ∑ k = 1 n P ( n , k ) = n ! + n ! 1 ! + n ! 2 ! + n ! 3 ! + … + n ! ( n − 1 ) ! < 2 n ! + n ! 2 + n ! 2 2 + n ! 2 n 2 < 3 n ! \\sum\_\{k=1\}^\{n\} P(n, k)=n !+\\frac\{n !\}\{1 !\}+\\frac\{n !\}\{2 !\}+\\frac\{n !\}\{3 !\}+\\ldots+\\frac\{n !\}\{(n-1) !\}<2 n !+\\frac\{n !\}\{2\}+\\frac\{n !\}\{2^\{2\}\}+\\frac\{n !\}\{2^\{n\} 2\}<3 n ! ∑k=1nP(n,k)=n!\+1!n!\+2!n!\+3!n!\+…\+(n−1)!n!<2n!\+2n!\+22n!\+2n2n!<3n!  
        , 这说明 backTracking 的调用次数是  O ( n ! ) O(n!) O(n!)的。
     *  而对于 backTracking调用的每个叶结点（最坏情况下没有重复数字共  n ! n! n!个），我们需要将当前答案使用  O ( n ) O(n) O(n)的时间复制到答案数组中，相乘得时间复杂度为  O ( n × n ! ) O(n×n!) O(n×n!)。
     *  因此时间复杂度为 O ( n × n ! ) O(n×n!) O(n×n!)。
 *  空间复杂度： O ( n ) O(n) O(n)。我们需要 O ( n ) O(n) O(n)的标记数组，同时在递归的时候栈深度会达到 O ( n ) O(n) O(n)，因此总空间复杂度为  O ( n + n ) = O ( 2 n ) = O ( n ) O(n+n)=O(2n)=O(n) O(n\+n)=O(2n)=O(n)。

##### 注：仅供学习参考！ #####

题目来源：[力扣][Link 1]

[46.]: https://blog.csdn.net/weixin_43412762/article/details/128160319
[19f41f7b3b844e5496271b541efa4294.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/31/c71d8830bfdc422cb75d1100f08e0be5.png
[fd582a9d0edb49fab277b64241f4da88.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/31/501d8cc8fd674f2b8836d45d63f694fc.png
[70ba4f24495546c9a9671aa977c64a4c.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/31/71d9e22c574447629551dcabac39a9cd.png
[n _ k -]: https://baike.baidu.com/item/%E6%8E%92%E5%88%97/7804523
[Link 1]: https://leetcode.cn/problems/permutations-ii/description/