leetcode题记-46.全排列

题目

给定一个没有重复数字的序列,返回其所有可能的全排列。

示例:

输入: [1,2,3]
输出:[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

来源:力扣(LeetCode)

题解

解这道题主要用了通过递归实现回溯的办法。
在处理数组的过程中,先确定当前正在遍历的位,例如第一位,那么就将每一位和第一位互换,然后在下一个递归过程中将第二位和其他数字依次替换,这样的过程和人类的思维几乎一样。

具体可以看这个leetcode 官方题解,讲的还是很具体的,还有动图可以看。

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
26
27
28
class Solution {
vector<vector<int>> res;
public:
vector<vector<int>> permute(vector<int>& nums) {
if (nums.size() == 0) return res;
if (nums.size() == 1) {
res.push_back(vector<int>{nums[0]});
return res;
}

process(nums, 0);
return res;
}

void process(vector<int> nums, int front) {
if (front == nums.size() - 1) {
res.push_back(nums);
}

for (int i = front; i < nums.size(); i++) {
vector<int> _nums = nums;
int temp = _nums[front];
_nums[front] = _nums[i];
_nums[i] = temp;
process(_nums, front + 1);
}
}
};

结果

执行用时 : 16 ms, 在所有 C++ 提交中击败了86.15%的用户
内存消耗 : 10.2 MB, 在所有 C++ 提交中击败了13.65%的用户

Author: SmallXeon
Link: https://hexo.chensmallx.top/2019/08/22/leetcode-46-permute/
Copyright Notice: All articles in this blog are licensed under CC BY-NC-SA 4.0 unless stating additionally.
一些推广链接
几个便宜量大的小✈场: FASTLINK, YToo, 论坛邀请注册: ,
便宜量大但是稳定性不足的VPS: , 价格略贵但好用的VPN: , ,