Leetcode 46 Permutations
Given a collection of distinct integers, return all possible permutations.
Example:
Input: [1,2,3]
Output:
[
[1,2,3],
[1,3,2],
[2,1,3],
[2,3,1],
[3,1,2],
[3,2,1]
]
求给定数组的所有排列，数组中不含有重复的数
method 1
写法一：每次添加一个数，进行递归回溯，递归结束之后要删去这个数，在同样的位置换下一个数，每次添加之前要检查这个数是否已经出现在序列中（来源于《算法竞赛入门经典》）
void helper(vector<int>& nums, vector<vector<int>>& ans, vector<int> tmp){
if (tmp.size() == nums.size()) ans.push_back(tmp);else{
for (int i = 0; i < nums.size(); i++){
if (find(tmp.begin(), tmp.end(), nums[i]) != tmp.end()) continue;tmp.push_back(nums[i]);helper(nums, ans, tmp);tmp.pop_back();}}
}vector<vector<int>> permute(vector<int>& nums) {
vector<vector<int>> ans;if (nums.size() == 0) return ans;for (int i = 0; i < nums.size(); i++){
vector<int> tmp;tmp.push_back(nums[i]);helper(nums, ans, tmp);}return ans;
}
method 2
写法二：每次递归，引入一个新的参数index，指示遍历的开始，这样就避免了检查要添加的数是否已经出现过
void function(vector<vector<int>>& re, vector<int> temp, int index){
if (index == temp.size())re.push_back(temp);for (int i = index; i<temp.size(); i++){
swap(temp[index], temp[i]); //不停地交换，得到新的序列function(re, temp, index + 1);swap(temp[index], temp[i]);}}
vector<vector<int>> permute2(vector<int>& nums) {
vector<vector<int>> re;if (nums.size() == 0)return re;function(re, nums, 0);return re;
}
Leetcode 47. Permutations II
Given a collection of numbers that might contain duplicates, return all possible unique permutations.
Example:
Input: [1,1,2]
Output:
[
[1,1,2],
[1,2,1],
[2,1,1]
]
与I不同在于，数组中可能会出现重复的数字，这时算法有所不同
method 1
写法一：在I的基础上，每次添加数之前，首先要记录tmp中该数出现的次数c1，再记录数组中该数出现的次数c2，只有c1<c2时，才能添加该数，这样才不会重复。而且还要先对数组排序，因为如果已经添加过第i个位置数num了，第i+1个位置上仍然是num，此时第i+1个位置的递归要省略，不然也会造成重复
void helper3(vector<int>& nums, vector<vector<int>>& ans, vector<int> tmp){
if (tmp.size() == nums.size()) ans.push_back(tmp);else{
for (int i = 0; i < nums.size(); i++){
if (!i || nums[i] != nums[i - 1]){
int c1 = 0, c2 = 0;for (int j = 0; j < tmp.size(); j++) {
if (nums[i] == tmp[j]) c1++; }for (int j = 0; j < nums.size(); j++) {
if (nums[i] == nums[j]) c2++; }if (c1 < c2){
tmp.push_back(nums[i]);helper3(nums, ans, tmp);tmp.pop_back();}}}}
}vector<vector<int>> permuteUnique(vector<int>& nums) {
sort(nums.begin(), nums.end());vector<vector<int>> ans;if (nums.size() == 0) return ans;vector<int> tmp;helper3(nums, ans, tmp);return ans;
}
method 2
写法二：还是用交换的思想，引入index参数表示数组开始的位置
void recursion(vector<int> num, int index, vector<vector<int> > &res) {
if (index == num.size() - 1) {
res.push_back(num);return;}for (int k = index; k < num.size(); k++) {
if (index != k && num[index] == num[k]) continue; //排序的前提下，如果是相同的字符/已经加入过的字符，为了避免重复，就不再加入了swap(num[index], num[k]);recursion(num, index + 1, res);}
}
vector<vector<int> > permuteUnique2(vector<int> &num) {
sort(num.begin(), num.end());vector<vector<int> >res;recursion(num, 0, res);return res;
}
Leetcode 31. Next Permutation
Implement next permutation, which rearranges numbers into the lexicographically next greater permutation of numbers.
If such arrangement is not possible, it must rearrange it as the lowest possible order (ie, sorted in ascending order).
The replacement must be in-place and use only constant extra memory.
Here are some examples. Inputs are in the left-hand column and its corresponding outputs are in the right-hand column.
eg:
1,2,3 → 1,3,2
3,2,1 → 1,2,3
1,1,5 → 1,5,1
给出已知一个排列，得到下一个比其大的排列
method 1
图文解释：
https://leetcode.com/problems/next-permutation/discuss/13994/Readable-code-without-confusing-ij-and-with-explanation
算法思想：
- 在从右往左看的递增序列中找到第一个pivot
- 从右往左找第一个大于pivot的元素a
- 交换pivot和a
- 对pivot右边的序列进行reverse
public void nextPermutation(int[] nums) {
int i = nums.length - 2;while (i >= 0 && nums[i + 1] <= nums[i])i--;if (i >= 0) {
int j = nums.length - 1;while (j >= 0 && nums[j] <= nums[i]) {
j--;}swap(nums, i, j);}reverse(nums, i + 1);}private void reverse(int[] nums, int start) {
int i = start, j = nums.length - 1;while (i < j) {
swap(nums, i, j);i++;j--;}}private void swap(int[] nums, int i, int j) {
int temp = nums[i];nums[i] = nums[j];nums[j] = temp;}
Leetcode 60. Permutation Sequence
The set [1,2,3,…,n] contains a total of n! unique permutations.
By listing and labeling all of the permutations in order, we get the following sequence for n = 3:
“123”
“132”
“213”
“231”
“312”
“321”
Given n and k, return the kth permutation sequence.
method 1
正常使用46题的思路，当选出第k个排列时，直接返回
void helper(vector<int>& nums, int& cur, int k, vector<int>& tmp){
if (tmp.size() == nums.size()){
cur++;}else{
for (int i = 0; i < nums.size(); i++){
if (find(tmp.begin(), tmp.end(), nums[i]) != tmp.end()) continue; //这样才可以得到正确的顺序，但是会超时tmp.push_back(nums[i]);helper(nums, cur, k, tmp);if (cur == k) return;tmp.pop_back();}}
}string getPermutation(int n, int k) {
vector<int> str;for (int i = 1; i <= n; i++)str.push_back(i);int cur = 0;vector<int> tmp;helper(str, cur, k, tmp);string vec;for (int i = 0; i < tmp.size(); i++)vec += ('0' + tmp[i]);return vec;
}
注意，这里只有采用这个写法，大小顺序才会对，如果采用swap+index的写法，大小顺序并不对
method 2
解释：https://leetcode.com/problems/permutation-sequence/discuss/191348/c%2B%2B-0ms-100-with-algorithm-explanation
因为是求第k个，所以可以根据大小关系直接求
string getPermutation2(int n, int k) {
string res;string nums = "123456789";int f[10] = {
1, 1, 2, 6, 24, 120, 720, 5040, 40320, 362880};--k;for (int i = n; i >= 1; --i) {
int j = k / f[i - 1];k %= f[i - 1];res.push_back(nums[j]);nums.erase(nums.begin() + j);}return res;
}
summary
- 如果是要求第k个，那么往往可以根据大小关系，利用求余操作求