首页 > 代码库 > [leetcode]Next Permutation
[leetcode]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, 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
基本思路:
本题要求当前排列的下一个排列,假设已经是最大的排列,则对排列进行又一次排序,返回最小排列。
此题基本的方法是找规律:怎样才干得到下一个排列?下一个排列有两个特征(暂未考虑已经是最大的排列的情况)
- 下个排列比当前排列要大。
- 下个排列是全部比当前排列大的中最小的那个
要实现这个有三个步骤:
- 我们要找增大哪一位才干使排列增大。
- 这一位增大到多少才干使增大的最少。
- 其它低位的排列怎么处理。
从低位依次比較A[i-1]与A[i],找到第一个A[i-1] <A[i] 交换A[i-1] 与其后大于A[i-1]的某位能够实现排列的增大。
在A[i-1]之后的低位找到比A[i-1]大的最小的A[j],交换A[i-1]和A[j].
交换了A[i-1]和A[j],就保证了排列会增大。对于A[i-1]后面的内容,进行从小到大排序就能够了。
代码:
void nextPermutation(vector<int> &num) { //C++ for(int i = num.size()-1; i > 0 ; i-- ) { if(num[i] > num[i-1]) { int min = num[i] - num[i-1]; int pos = i; for(int k = i+1; k <num.size(); k++) { if(num[k] - num[i-1] < min && num[k] - num[i-1] >0) { min = num[k] - num[i-1]; pos = k; } } int tmp = num[pos]; num[pos] = num[i-1]; num[i-1] = tmp; sort(num.begin()+i,num.end()); return; } } sort(num.begin(),num.end()); }
[leetcode]Next Permutation
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。