【LeetCode】46. Permutations 解題報告

46. Permutations / Medium

Given an array nums of distinct integers, return all the possible permutations. You can return the answer in any order.

Example 1:

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

Example 2:

Input: nums = [0,1]
Output: [[0,1],[1,0]]

Example 3:

Input: nums = [1]
Output: [[1]]

Constraints:

  • 1 <= nums.length <= 6
  • -10 <= nums[i] <= 10
  • All the integers of nums are unique.

Solution 1: C++ implementation of next_permutation

思路

C++ 內建一個函式叫 next_permutation,每次呼叫都會給回傳給定陣列的下一個排列。
面試時應該是無法使用這個函式,而 C++ 的 next_permutataion 實作過程如下動畫。

時間複雜度是 O(N・N!),因為排列有 N! 種,每次都必須用 O(N) 去找出下一個排列,所以總共是 O(N・N!)次。
最好的狀態是陣列中全都是相同的值,最壞的狀態是每一個值都不同。

效能

Complexity

  • Time Complexity: O(N ・ N!), where N is the length of nums.
  • Space Complexity: O(1), not containing return value.

LeetCode Result

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
public:
vector<vector<int>> permute(vector<int>& nums) {
vector<vector<int>> permutations;
sort(nums.begin(), nums.end());
do {
permutations.emplace_back(nums);
} while(NextPermutation(nums));
return permutations;
}

bool NextPermutation(vector<int>& nums) {
if(nums.size() <= 1) return false;
int i = nums.size()-2;
while((i >= 0) && (nums[i] >= nums[i+1])) --i;
if(i < 0) return false;
if(i >= 0) {
int j = nums.size()-1;
while((j >= i) && (nums[j] <= nums[i])) --j;
swap(nums[i], nums[j]);
}
reverse(nums.begin()+i+1, nums.end());
return true;
}
};

Solution 2: Bactracking

思路

比較直覺也比較容易實作的方式是用 Backtracking。
每次都將目前標記的位置(從第一個開始,程式中的 first),然後依序和後面所有的值都交換一次,接著進入下一個狀態。最 first+1 的位置開始往後做交換。

效能

Complexity

LeetCode Result

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
vector<vector<int>> permute(vector<int>& nums) {
permutate(nums, 0);
return permutations;
}

void permutate(vector<int>& nums, int first){
if(nums.size() == first) {
permutations.emplace_back(nums);
return;
}

for(int i = first; i < nums.size(); ++i) {
swap(nums[i], nums[first]);
permutate(nums, first+1);
swap(nums[i], nums[first]);
}
}

private:
vector<vector<int>> permutations;
};