Leetcode 31. Next Permutation

文章作者:Tyan
博客:noahsnail.com  |  CSDN  |  简书

1. Description

Next Permutation

2. Solution

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
29
30
31
class Solution {
public:
void nextPermutation(vector<int>& nums) {
int index = -1;
int min = 0;
for(int i = nums.size() - 1; i > 0; i--) {
if(nums[i] > nums[i - 1] ) {
index = i - 1;
min = i;
break;
}
}
if(index == -1) {
return reverse(nums.begin(), nums.end());
}
for(int i = index + 1; i < nums.size(); i++) {
if(nums[i] > nums[index] && nums[i] < nums[min]) {
min = i;
}
}
swap(nums[index], nums[min]);
sort(nums.begin() + index + 1, nums.end());
}
private:
void swap(int& a, int& b) {
int temp = a;
a = b;
b = temp;
}
};

Reference

  1. https://leetcode.com/problems/next-permutation/description/
如果有收获,可以请我喝杯咖啡!