小程序平臺(tái)商城seo搜索引擎優(yōu)化實(shí)戰(zhàn)
描述
給出一組數(shù)字,返回該組數(shù)字的所有排列
例如:
[1,2,3]的所有排列如下
[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2], [3,2,1].
(以數(shù)字在數(shù)組中的位置靠前為優(yōu)先級(jí),按字典序排列輸出。)
數(shù)據(jù)范圍:數(shù)字個(gè)數(shù)?0<n≤6
要求:空間復(fù)雜度?O(n!),時(shí)間復(fù)雜度?O(n!)
示例1
輸入:
[1,2,3]
返回值:
[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
示例2
輸入:
[1]
返回值:
[[1]]
思路分析:
經(jīng)典的回溯算法問題——全排列(Permutations)
-
permute
?方法:這是類的公共方法,接收一個(gè)整數(shù)數(shù)組?num
?作為輸入,并返回一個(gè)?ArrayList<ArrayList<Integer>>
?類型的列表,其中每個(gè)內(nèi)部列表代表?num
?數(shù)組的一個(gè)排列。- 初始化一個(gè)?
ArrayList<ArrayList<Integer>>
?類型的?result
?列表,用于存儲(chǔ)所有排列。 - 初始化一個(gè)?
LinkedList<Integer>
?類型的?list
,用于在回溯過程中構(gòu)建當(dāng)前的排列。 - 調(diào)用?
backTrack
?方法開始回溯過程。
- 初始化一個(gè)?
-
backTrack
?方法:這是一個(gè)私有方法,用于遞歸地生成所有排列。它接收三個(gè)參數(shù):-
num
:原始整數(shù)數(shù)組。 -
list
:當(dāng)前正在構(gòu)建的排列(以鏈表形式)。 -
result
:用于存儲(chǔ)所有排列的列表。 -
遞歸終止條件:如果?
list
?的大小等于?num
?的長(zhǎng)度,說明已經(jīng)構(gòu)建了一個(gè)完整的排列,此時(shí)將這個(gè)排列(通過?new ArrayList<Integer>(list)
?轉(zhuǎn)換為不可變列表)添加到?result
?中,并返回。 -
遞歸過程:遍歷?
num
?數(shù)組中的每個(gè)元素,如果當(dāng)前元素已經(jīng)存在于?list
?中,則跳過該元素(避免重復(fù)排列)。否則,將該元素添加到?list
?中,并遞歸調(diào)用?backTrack
?方法繼續(xù)構(gòu)建下一個(gè)元素。遞歸返回后,需要撤銷上一步的選擇(即移除?list
?中最后添加的元素),以便嘗試其他可能的排列。
-
代碼:
import java.util.*;public class Solution {public ArrayList<ArrayList<Integer>> permute(int[] num) {ArrayList<ArrayList<Integer>> result = new ArrayList<>();LinkedList<Integer> list = new LinkedList<>();backTrack(num, list, result);return result;}private void backTrack(int[] num, LinkedList<Integer> list,ArrayList<ArrayList<Integer>> result) {if (list.size() == num.length) {result.add(new ArrayList<Integer>(list));return;}for (int i = 0; i < num.length; i++) {if (list.contains(num[i])) {continue;}list.add(num[i]);backTrack(num, list, result);list.removeLast();}}
}