【LeetCode】031. Next Permutation
2024-08-26 01:44:03
题目：
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, do not allocate extra memory.
Here are some examples. Inputs are in the left-hand column and its corresponding outputs are in the right-hand column.
1,2,3 → 1,3,2
3,2,1 → 1,2,3
1,1,5 → 1,5,1
题解：
from here
Solution 1 ()
class Solution {
public:
void nextPermutation(vector<int>& nums) {
int n = nums.size();
for(int i=n-; i>=; --i) {
if(nums[i]>=nums[i+]) continue;
int j = n-;
for(; j>i; --j) {
if(nums[j]>nums[i]) break;
}
swap(nums[i], nums[j]);
reverse(nums.begin()+i+, nums.end());
return;
}
reverse(nums.begin(), nums.end());
}
};
from here
Solution 2 ()
class Solution {
public:
void nextPermutation(vector<int> &nums) {
if (nums.empty()) return;
// in reverse order, find the first number which is in increasing trend (we call it violated number here)
int i;
for (i = nums.size()-; i >= ; --i) {
if (nums[i] < nums[i+]) break;
}
// reverse all the numbers after violated number
reverse(nums.begin()+i+, nums.end());
// if violated number not found, because we have reversed the whole array, then we are done!
if (i == -) return;
// else binary search find the first number larger than the violated number
auto itr = upper_bound(nums.begin()+i+, nums.end(), nums[i]);
// swap them, done!
swap(nums[i], *itr);
}
};
Solution 3-5 are from here (Solution 2 和 Solution 3 其实是一个解法 )
Solution 3 ()
class Solution {
public:
void nextPermutation(vector<int>& nums) {
int i = nums.size() - , k = i;
while (i > && nums[i-] >= nums[i])
i--;
for (int j=i; j<k; j++, k--)
swap(nums[j], nums[k]);
if (i > ) {
k = i--;
while (nums[k] <= nums[i])
k++;
swap(nums[i], nums[k]);
}
}
};
使用STL库函数
Solution 4 ()
class Solution {
public:
void nextPermutation(vector<int>& nums) {
auto i = is_sorted_until(nums.rbegin(), nums.rend());
if (i != nums.rend())
swap(*i, *upper_bound(nums.rbegin(), i, *i));
reverse(nums.rbegin(), i);
}
};
使用STL库函数
Solution 5 ()
class Solution {
public:
void nextPermutation(vector<int>& nums) {
next_permutation(begin(nums), end(nums));
}
};
最新文章
- Salesforce开发者学习笔记之一:基本知识
- Git的checkout, reset, revert
- Rest(表述性状态转移)
- Python之路-python(Queue队列、进程、Gevent协程、Select\Poll\Epoll异步IO与事件驱动)
- 【ArcGis for javascript从零开始】之一 ArcGis加载天地图
- java中的substring用法
- Android Studio修改包名和applicationId的方法
- 做一款仿映客的直播App？看我就够了
- vi 或 vim 常用命令（简单够用了）
- Unix文件操作
- Linux学习——卸载Ubuntu，安装CentOS，第一次使用命令
- redis 未授权漏洞利用直接登录服务器
- Unity3d在线游戏Socket通讯
- 一.HttpClient、JsonPath、JsonObject运用
- volatile可见性的一些认识
- 读书笔记-你不知道的JS中-promise(2)
- RESTful协议
- 如何用 Node.js 和 Elasticsearch 构建搜索引擎
- 51Nod 最小公倍数之和V3
- python之多线程举例