文章目錄

• 1題目理解
• 2 回溯
• 3 47. Permutations II

1題目理解

Given an array nums of distinct integers, return all the possible permutations. You can return the answer in any order.
輸入：整數(shù)數(shù)組nums，所有元素不相同
輸出：數(shù)組的所有可能的排列

例如:
Input: nums = [1,2,3]
Output: [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

2 回溯

所有排列是指nums中的每一個元素，在每個位置都會出現(xiàn)一次。
有一個長度為n的空數(shù)組，第0位元素可能是1、2、3任意一個。第1位也一樣。但是這里前面的位置選了的元素，在后面位置就不能使用了。所以，我們可以用一個數(shù)組記錄哪些元素已經(jīng)被使用過。

class Solution {private List<List<Integer>> answer;private boolean[] visited;private int[] nums;public List<List<Integer>> permute(int[] nums) {answer = new ArrayList<List<Integer>>();this.nums = nums;visited = new boolean[nums.length];dfs(0,new int[nums.length]);return answer;}private void dfs(int index,int[] items){if(index == this.nums.length){List<Integer> list = new ArrayList<Integer>();for(int n : items){list.add(n);}answer.add(list);return;}for(int i =0;i<nums.length;i++){if(!visited[i]){visited[i] = true;items[index] = nums[i];dfs(index+1,items);visited[i]=false;}}} }

時間復雜度$O(n?n!)$。首先dfs調(diào)用次數(shù)是n！。在最后結(jié)果放入結(jié)果集有一個拷貝操作n。所以最終是$O(n?n!)$。

3 47. Permutations II

與46類似，但是輸入nums可能包含重復元素。
例如：
Input: nums = [1,1,2]
Output:
[[1,1,2],
[1,2,1],
[2,1,1]]
分析：重復元素之前有處理經(jīng)驗了。對數(shù)組先排序。
對于第0個位置的元素可能是1、2。選擇了第一個1，第二個1就可以跳過了。否則就重復了。
代碼只要在之前代碼上改一下即可。

class Solution {private List<List<Integer>> answer;private boolean[] visited;private int[] nums;public List<List<Integer>> permuteUnique(int[] nums) {answer = new ArrayList<List<Integer>>();Arrays.sort(nums);this.nums = nums;visited = new boolean[nums.length];dfs(0,new int[nums.length]);return answer;}private void dfs(int index,int[] items){if(index == this.nums.length){List<Integer> list = new ArrayList<Integer>();for(int n : items){list.add(n);}answer.add(list);return;}for(int i = 0;i<nums.length;i++){if(!visited[i]){visited[i] = true;items[index] = nums[i];dfs(index+1,items);visited[i]=false;while(i+1<nums.length && nums[i+1]==nums[i]) i++;}}} }

時間復雜度最壞情況下上$O(n?n!)$。首先dfs調(diào)用次數(shù)是n！。在最后結(jié)果放入結(jié)果集有一個拷貝操作n。所以最終是$O(n?n!)$。

創(chuàng)作挑戰(zhàn)賽新人創(chuàng)作獎勵來咯，堅持創(chuàng)作打卡瓜分現(xiàn)金大獎

總結(jié)

以上是生活随笔為你收集整理的46. Permutations的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。