LeetCode 46 Permutations + LeetCode 47 Permutations II

本文主要是介绍LeetCode 46 Permutations + LeetCode 47 Permutations II，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题意：

给出一串（46题）不重复or（47题）有重复的数字，要求输出所有排列。

思路：

有没有重复不影响思路 = =。 代码展示为46题提交结果，47题一样过……

可以偷懒用next_permutation方法也可以自己实现，实现方法为从后往前找第一个出现的nums[i] < nums[i+1]，从i后面找出比nums[i]稍大一点的数字nums[x]，交换nums[i]和nums[x]，反序i后面的部分。

代码：

/*** 自己实现 13ms*/class Solution {
public:vector<vector<int>> permute(vector<int> &nums) {vector<vector<int>> ans;sort(nums.begin(), nums.end());ans.push_back(nums);for (;;) {int id = -1;for (int i = nums.size() - 1; i > 0; --i) {if (nums[i] > nums[i - 1]) {id = i - 1;break;}}if (id == -1) {break;}for (int i = nums.size() - 1;; --i) {if (nums[i] > nums[id]) {swap(nums[i], nums[id]);reverse(nums.begin() + id + 1, nums.end());break;}}ans.push_back(nums);}return ans;}
};/*** 偷懒用next_permutation 19ms*/class Solution {
public:vector<vector<int>> permute(vector<int> &nums) {vector<vector<int>> ans;sort(nums.begin(), nums.end());ans.push_back(nums);while (next_permutation(nums.begin(), nums.end())) {ans.push_back(nums);}return ans;}
};

这篇关于LeetCode 46 Permutations + LeetCode 47 Permutations II的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---