威海高区建设局网站,广州越秀建网站的公司,去哪里投诉百度公司,网站搭建类型给定一个不含重复数字的整数数组 nums #xff0c;返回其 所有可能的全排列 。可以 按任意顺序 返回答案。
示例 1#xff1a;
输入#xff1a;nums [1,2,3] 输出#xff1a;[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
1 nums.length 6 -10 nu…给定一个不含重复数字的整数数组 nums 返回其 所有可能的全排列 。可以 按任意顺序 返回答案。
示例 1
输入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 6 -10 nums[i] 10 nums 中的所有整数 互不相同
解法一直接使用STL
class Solution {
public:vectorvectorint permute(vectorint nums) {// next_permutation函数每次产生下一个排列// 下一个排列的含义是按字典顺序下一个更大的排列// 因此需要先对nums进行从小到大排序sort(nums.begin(), nums.end());vectorvectorint ans;do {ans.push_back(nums);} while (next_permutation(nums.begin(), nums.end()));return ans;}
};如果输入数组大小为n此算法时间复杂度为On*n!空间复杂度为O1。next_permutation函数的时间复杂度最多为On。
解法二回溯法遍历某个排列的每一个元素当遍历到下标i时我们遍历所有可以放到下标i的元素但有些元素在前面已经用过了因此我们维护一个visited数组如果该元素没有用过才放到下标i
class Solution {
public:vectorvectorint permute(vectorint nums) {vectorvectorint ans;unordered_setint visited;vectorint current;backtrack(0, current, nums, visited, ans);return ans;}private:void backtrack(int pos, vectorint current, vectorint nums, unordered_setint visited, vectorvectorint ans) {int sz nums.size();if (pos sz) {ans.push_back(current);}for (int i 0; i sz; i) {if (visited.find(nums[i]) ! visited.end()) {continue;}visited.insert(nums[i]);current.push_back(nums[i]);backtrack(pos 1, current, nums, visited, ans);current.pop_back();visited.erase(nums[i]);}}
};如果输入数组大小为n此算法时间复杂度为On*n!空间复杂度为On。backtrack函数的调用次数为On!每次调用中会循环n次。对于空间复杂度递归深度为n主要开销是栈空间开销和current、visited数组开销。
解法三在解法二中我们使用了visited数组来标记哪些元素已经被全排列过了我们可以直接修改nums数组当遍历到下标i时我们可以令[0,i]的所有元素都是已经全排列过的元素具体做法是将当前循环中要排列的元素和下标为i的元素交换
class Solution {
public:vectorvectorint permute(vectorint nums) {vectorvectorint ans;backtrack(0, nums, ans);return ans;}private:void backtrack(int pos, vectorint nums, vectorvectorint ans) {int sz nums.size();if (pos sz) {ans.push_back(nums);}for (int i pos; i sz; i) {swap(nums[i], nums[pos]);backtrack(pos 1, nums, ans);swap(nums[i], nums[pos]);}}
};如果输入数组大小为n此算法时间复杂度为On*n!空间复杂度为On。backtrack函数的调用次数为On!每次调用中会循环n次。对于空间复杂度递归深度为n主要开销是栈空间开销。
