47.全排列II-創(chuàng)新互聯(lián)

關(guān)上過(guò)去和未來(lái)的鐵門，活在“今天”這個(gè)艙室中。 ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?——《人性的優(yōu)點(diǎn)》

創(chuàng)新互聯(lián)公司 - 服務(wù)器機(jī)柜租用，四川服務(wù)器租用，成都服務(wù)器租用，四川網(wǎng)通托管,綿陽(yáng)服務(wù)器托管，德陽(yáng)服務(wù)器托管，遂寧服務(wù)器托管，綿陽(yáng)服務(wù)器托管，四川云主機(jī)，成都云主機(jī)，西南云主機(jī)，服務(wù)器機(jī)柜租用，西南服務(wù)器托管，四川/成都大帶寬，大帶寬服務(wù)器，四川老牌ＩＤＣ服務(wù)商

47. 全排列 II

給定一個(gè)可包含重復(fù)數(shù)字的序列 nums ，按任意順序 返回所有不重復(fù)的全排列。

示例 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. 全排列 的進(jìn)階

• 但是這道題有了一點(diǎn)改變，那么就是列表里面有重復(fù)數(shù)字，全排列的結(jié)果，相同答案只算一種，那么我們就要考慮重復(fù)。
• 當(dāng)然因?yàn)轭}目沒(méi)有說(shuō)該隊(duì)列有序，所以要先排序。

判斷的時(shí)候加上：

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

其中最為關(guān)鍵的是 hasVisited[i-1] == false ，用來(lái)去重，就是限制一下兩個(gè)相鄰的重復(fù)的訪問(wèn)順序

舉個(gè)栗子 ：

對(duì)于兩個(gè)相同的數(shù) 1 1 ，我們將其命名為 a b，a 表示第一個(gè) 1 ，b 表示第二個(gè) 1

• 如果不去重得的話，會(huì)有兩種重復(fù)排列 a b，b a ，我們只需取其中任意一種排列即可；
• 為了達(dá)到目的，限制一下 a ，b 的訪問(wèn)順序即可；
• 比如 我們只取 a b 這個(gè)排列的話，只有當(dāng) nums[i - 1] 訪問(wèn)后，我們才去訪問(wèn) nums[i] ，
• 也就是說(shuō) 如果 hasVisited[i-1] == false 的話， 則 continue 跳過(guò)。

舉另個(gè)栗子 ：

去重最為關(guān)鍵的代碼為：

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 ，是對(duì)樹層中前一位去重；
• hasVisited[i-1] == true ，是對(duì)樹枝前一位去重；

（借用一下別人的圖進(jìn)行理解）：

如果 是三個(gè)相同的數(shù) 1 1 1

樹層上去重（hasVisited[i-1] == false），樹形結(jié)構(gòu)如下：

樹枝上去重（hasVisited[i-1] == true），樹形結(jié)構(gòu)如下：

觀察上圖可以得出：

• 樹層上對(duì)前一位去重非常徹底，效率很高；
• 樹枝上對(duì)前一位去重雖然最后可以得到答案，但是做了很多無(wú)用搜索。

代碼：（Java）

import java.util.ArrayList;
import java.util.List;

public class all_permute {public static void main(String[] args) {// TODO 自動(dòng)生成的方法存根
		int [] nums = {1, 1, 2};
		System.out.println(permuteUnique(nums));
	}
	public static List>permuteUnique(int[] nums) {List>permutes = new ArrayList<>();
		Listpermute = new ArrayList<>();
		if(nums == null || nums.length == 0) {	return permutes;
		}
		int flag = 0;//標(biāo)記
		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, Listpermute, List>permutes) {// TODO 自動(dòng)生成的方法存根
		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;
		}
	}
}

運(yùn)行結(jié)果：

復(fù)雜度分析：

• 時(shí)間復(fù)雜度： O ( n × n ! ) O(n×n!) O(n×n!)，其中 n 為序列的長(zhǎng)度。

  • 算法的復(fù)雜度首先受 backTracking 的調(diào)用次數(shù)制約，backTracking 的調(diào)用次數(shù)為 ∑ k = 1 n P ( n , k ) \sum_{k=1}^{n} P(n, k) ∑k=1n?P(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 - 排列，或者部分排列。

  • 而 ∑ 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=1n?P(n,k)=n!+1!n!?+2!n!?+3!n!?+…+(n?1)!n!?<2n!+2n!?+22n!?+2n2n!?<3n!
    , 這說(shuō)明 backTracking 的調(diào)用次數(shù)是 O ( n ! ) O(n!) O(n!)的。

  • 而對(duì)于 backTracking調(diào)用的每個(gè)葉結(jié)點(diǎn)（最壞情況下沒(méi)有重復(fù)數(shù)字共 n ! n! n!個(gè)），我們需要將當(dāng)前答案使用 O ( n ) O(n) O(n)的時(shí)間復(fù)制到答案數(shù)組中，相乘得時(shí)間復(fù)雜度為 O ( n × n ! ) O(n×n!) O(n×n!)。

  • 因此時(shí)間復(fù)雜度為 O ( n × n ! ) O(n×n!) O(n×n!)。

• 空間復(fù)雜度： O ( n ) O(n) O(n)。我們需要 O ( n ) O(n) O(n)的標(biāo)記數(shù)組，同時(shí)在遞歸的時(shí)候棧深度會(huì)達(dá)到 O ( n ) O(n) O(n)，因此總空間復(fù)雜度為 O ( n + n ) = O ( 2 n ) = O ( n ) O(n+n)=O(2n)=O(n) O(n+n)=O(2n)=O(n)。

注：僅供學(xué)習(xí)參考！

題目來(lái)源：力扣

你是否還在尋找穩(wěn)定的海外服務(wù)器提供商？創(chuàng)新互聯(lián)www.cdcxhl.cn海外機(jī)房具備T級(jí)流量清洗系統(tǒng)配攻擊溯源，準(zhǔn)確流量調(diào)度確保服務(wù)器高可用性，企業(yè)級(jí)服務(wù)器適合批量采購(gòu)，新人活動(dòng)首月15元起，快前往官網(wǎng)查看詳情吧

文章標(biāo)題：47.全排列II-創(chuàng)新互聯(lián)
網(wǎng)址分享：http://bm7419.com/article36/geepg.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供自適應(yīng)網(wǎng)站、做網(wǎng)站、網(wǎng)站收錄、品牌網(wǎng)站設(shè)計(jì)、網(wǎng)站建設(shè)、企業(yè)網(wǎng)站制作

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請(qǐng)盡快告知，我們將會(huì)在第一時(shí)間刪除。文章觀點(diǎn)不代表本網(wǎng)站立場(chǎng)，如需處理請(qǐng)聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時(shí)需注明來(lái)源： 創(chuàng)新互聯(lián)