DAY 14
0

## 前言(廢話)

31題是求下一個排列。

#46 Permutations
#47 Permutations II

## 36 NEXT PERMUTATION

[1,2,3]→[1,3,2]
[1,5,3]→[3,1,5]
[9,8,7]→[7,8,9]

### 思維

123 → 132 → 213 → 231 → 312 → 321 → 123

### 程式碼

``````class Solution {
public:
void nextPermutation(vector<int>& nums) {
for(int i=nums.size()-1;i>0;i--)
{
if(nums[i-1]<nums[i])
{
int anchor=nums[i];
int j=i,e=i;
while(j<nums.size())
{
if(anchor>nums[j]&&nums[j]>nums[i-1])
{anchor=nums[j];e=j;}
j++;
}
nums.erase(nums.begin()+e);
nums.insert(nums.begin()+i-1,anchor);
sort(nums.begin()+i,nums.end());
return;
}
}
sort(nums.begin(),nums.end());
}
};
``````

## 46 Permutations

### 程式碼

``````class Solution {
public:
vector<vector<int>> permute(vector<int>& nums) {
vector<vector<int>> ans;
vector<int> end=nums;
do{
nums=nextPermutation(nums);
ans.push_back(nums);
}while(end!=nums);
sort(ans.begin(),ans.end());
return ans;
}
vector<int> nextPermutation(vector<int> nums) {
for(int i=nums.size()-1;i>0;i--)
{
if(nums[i-1]<nums[i])
{
int anchor=nums[i];
int j=i,e=i;
while(j<nums.size())
{
if(anchor>nums[j]&&nums[j]>nums[i-1])
{anchor=nums[j];e=j;}
j++;
}
nums.erase(nums.begin()+e);
nums.insert(nums.begin()+i-1,anchor);
sort(nums.begin()+i,nums.end());
return nums;
}
}
sort(nums.begin(),nums.end());
return nums;
}
};
``````

## 47 Permutations II

### 思維

``````class Solution {
public:
vector<vector<int>> permuteUnique(vector<int>& nums) {
vector<vector<int>> ans;
vector<int> end=nums;
do{
nums=nextPermutation(nums);
ans.push_back(nums);
}while(end!=nums);
sort(ans.begin(),ans.end());
return ans;
}
vector<int> nextPermutation(vector<int> nums) {
for(int i=nums.size()-1;i>0;i--)
{
if(nums[i-1]<nums[i])
{
int anchor=nums[i];
int j=i,e=i;
while(j<nums.size())
{
if(anchor>nums[j]&&nums[j]>nums[i-1])
{anchor=nums[j];e=j;}
j++;
}
nums.erase(nums.begin()+e);
nums.insert(nums.begin()+i-1,anchor);
sort(nums.begin()+i,nums.end());
return nums;
}
}
sort(nums.begin(),nums.end());
return nums;
}
};
``````