当前位置:网站首页>Leetcode (46) - Full Permutation
Leetcode (46) - Full Permutation
2022-07-07 05:16:00 【SmileGuy17】
Leetcode(46)—— Full Permutation
subject
Give an array without duplicate numbers nums , Back to its All possible permutations . You can In any order Return to the answer .
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]]
Tips :
- 1 1 1 <= nums.length <= 6 6 6
- − 10 -10 −10 <= nums[i] <= 10 10 10
- n u m s nums nums All integers in Different from each other
Answer key
Method 1 : backtracking
Ideas
How to output all the permutations ? For each current location i, We can swap them anywhere after , Then continue processing the location i+1, Until the last one . In order to prevent every traversal Create a new sub array Storage location i Numbers that have been exchanged before —— We can Using backtracking , Only modify the original array , After the recursion is completed, modify it back .
say concretely , Let's say we've filled in page first \textit{first} first A place , that nums \textit{nums} nums Array [ 0 , first − 1 ] [0, \textit{first} - 1] [0,first−1] Is a collection of filled numbers , [ first , n − 1 ] [\textit{first}, n - 1] [first,n−1] Is the set of numbers to be filled . We must be trying to use [ first , n − 1 ] [\textit{first}, n - 1] [first,n−1] Fill in the number in first \textit{first} first Number , Suppose the subscript of the number to be filled is i i i, Then when we're done, we'll go to the i i i Number and number first \textit{first} first Number exchange , That is, it can make it possible to first + 1 \textit{first} + 1 first+1 When we count nums \textit{nums} nums Array of [ 0 , first ] [0, \textit{first}] [0,first] Part is the number filled in , [ first + 1 , n − 1 ] [\textit{first} + 1, n - 1] [first+1,n−1] Is the number to be filled in , When you backtrack, you can complete the undo operation by switching back .
A simple example , Suppose we have [ 2 , 5 , 8 , 9 , 10 ] [2, 5, 8, 9, 10] [2,5,8,9,10] this 5 5 5 The number should be filled in , It has been filled in to 3 3 3 A place , It has been filled in [ 8 , 9 ] [8, 9] [8,9] Two Numbers , So this array is now [ 8 , 9 ∣ 2 , 5 , 10 ] [8, 9~|~2, 5, 10] [8,9 ∣ 2,5,10] Such a state , The separator separates the left and right parts . Suppose we fill in this position 10 10 10 The number of , To maintain the array , We will 2 2 2 and 10 10 10 In exchange for , That is, the array can continue to keep the number to the left of the separator has been filled , The one on the right is to be filled in [ 8 , 9 , 10 ∣ 2 , 5 ] [8, 9, 10~|~2, 5] [8,9,10 ∣ 2,5].
Of course, we will find that the resulting full permutation is not stored in the answer array in dictionary order , If the title requires output in dictionary order , Then please use tag array or other methods .
The following figure shows the whole process of backtracking :
Code implementation
Leetcode Official explanation :
class Solution {
public:
void backtrack(vector<vector<int>>& res, vector<int>& output, int first, int len){
// All the numbers have been filled in
if (first == len) {
res.emplace_back(output);
return;
}
for (int i = first; i < len; ++i) {
// Dynamically maintain arrays
swap(output[i], output[first]);
// Continue to recursively fill in the next number
backtrack(res, output, first + 1, len);
// Cancel the operation
swap(output[i], output[first]);
}
}
vector<vector<int>> permute(vector<int>& nums) {
vector<vector<int> > res;
backtrack(res, nums, 0, (int)nums.size());
return res;
}
};
My own :
class Solution {
void DFS(vector<vector<int>>& ans, vector<int>& s, vector<int>& nums, int p){
if(s.size() == nums.size()) ans.push_back(s);
else{
for(int n = p; n < nums.size(); n++){
swap(nums[p], nums[n]);
s.push_back(nums[p]);
DFS(ans, s, nums, p+1); // From the subscript 1 Start
s.pop_back(); // to flash back
swap(nums[p], nums[n]);
}
}
}
public:
vector<vector<int>> permute(vector<int>& nums) {
vector<int> s;
vector<vector<int>> ans;
DFS(ans, s, nums, 0);
return ans;
}
};
After improvement :
class Solution {
void DFS(vector<vector<int>>& ans, vector<int>& nums, int p){
if(p+1 == nums.size())
ans.push_back(nums);
else{
for(int n = p; n < nums.size(); n++){
swap(nums[p], nums[n]);
DFS(ans, nums, p+1); // From the subscript p+1 Start
swap(nums[p], nums[n]); // to flash back
}
}
}
public:
vector<vector<int>> permute(vector<int>& nums) {
vector<vector<int>> ans;
DFS(ans, nums, 0);
return ans;
}
};
Complexity analysis
- Time complexity : O ( n × n ! ) O(n \times n!) O(n×n!), among n n n Is the length of the sequence .
The complexity of the algorithm is first affected by backtrack \textit{backtrack} backtrack The number of calls is limited , backtrack \textit{backtrack} backtrack The number of calls to is ∑ k = 1 n P ( n , k ) \sum_{k = 1}^{n}{P(n, k)} ∑k=1nP(n,k) Time , among 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), This formula is called n Of k - array , Or partially arranged .
and ∑ 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)!} < 2n! + \frac{n!}{2} + \frac{n!}{2^2} + \frac{n!}{2^{n-2}} < 3n! ∑k=1nP(n,k)=n!+1!n!+2!n!+3!n!+…+(n−1)!n!<2n!+2n!+22n!+2n−2n!<3n!
This explanation backtrack \textit{backtrack} backtrack The number of calls is O ( n ! ) O(n!) O(n!) Of .
And for backtrack \textit{backtrack} backtrack Each leaf node called ( common n ! n! n! individual ), We need to use the current answer O ( n ) O(n) O(n) Copy the time to the answer array , The time complexity of multiplication is O ( n × n ! ) O(n \times n!) O(n×n!).
So the time complexity is zero O ( n × n ! ) O(n \times n!) O(n×n!). - Spatial complexity : O ( n ) O(n) O(n), among n n n Is the length of the sequence . Except for the answer array , Recursive functions in the recursive process need to allocate stack space for each layer of recursive functions , So extra space is needed here, and that space depends on the depth of the recursion , Here we can see that the recursive call depth is O ( n ) O(n) O(n).
边栏推荐
- [ArcGIS tutorial] thematic map production - population density distribution map - population density analysis
- Ansible中的inventory主机清单(预祝你我有数不尽的鲜花和浪漫)
- 基于Bevy游戏引擎和FPGA的双人游戏
- Batch normalization (Standardization) processing
- ClickHouse(03)ClickHouse怎么安装和部署
- Leetcode(417)——太平洋大西洋水流问题
- 模拟线程通信
- Leetcode(46)——全排列
- Is PMP really useful?
- Full link voltage test: the dispute between shadow database and shadow table
猜你喜欢
Time complexity & space complexity
Is it necessary to renew the PMP certificate?
《四》表单
pmp真的有用吗?
【愚公系列】2022年7月 Go教学课程 005-变量
Auto. JS get all app names of mobile phones
QT simple layout box model with spring
How to design API interface and realize unified format return?
Ansible overview and module explanation (you just passed today, but yesterday came to your face)
- [email protected] Mapping relatio"/>
Why JSON is used for calls between interfaces, how fastjson is assigned, fastjson 1.2 [email protected] Mapping relatio
随机推荐
Flask project uses flask socketio exception: typeerror: function() argument 1 must be code, not str
No experts! Growth secrets for junior and intermediate programmers and "quasi programmers" who are still practicing in Universities
Markdown editor
AttributeError: module ‘torch._ C‘ has no attribute ‘_ cuda_ setDevice‘
10 distributed databases that take you to the galaxy
The founder has a debt of 1billion. Let's start the class. Is it about to "end the class"?
Weebly移动端网站编辑器 手机浏览新时代
Why do many people misunderstand technical debt
3. Type of fund
LinkedBlockingQueue源码分析-初始化
CentOS 7.9安装Oracle 21c历险记
在米家、欧瑞博、苹果HomeKit趋势下,智汀如何从中脱颖而出?
Linkedblockingqueue source code analysis - initialization
Leetcode(417)——太平洋大西洋水流问题
Window scheduled tasks
The most complete learning rate adjustment strategy in history LR_ scheduler
QT simple layout box model with spring
Ansible中的inventory主機清單(預祝你我有數不盡的鮮花和浪漫)
Understand common network i/o models
DBSync新增对MongoDB、ES的支持