网站建设销售发展前景,甘肃住房和城乡建设局网站,十堰网站建设u2028,建怎样的网站挣钱快LeetCode#xff1a;31. 下一个排列 字典序的大小排序#xff1a;
从前往后对比#xff0c;如果先出现更小字符的#xff0c;字典序更小#xff0c;如果有个字符串结束了#xff0c;则它更小。string s 112233和string t 1122334#xff0c;…LeetCode31. 下一个排列 字典序的大小排序
从前往后对比如果先出现更小字符的字典序更小如果有个字符串结束了则它更小。string s 112233和string t 1122334s更小
根据字典序排序说法我们想找到尽可能小的比当前字典序大的字符串我们就要尽可能的使得字典序大的出现在更右边。
我们考虑极端情况如1122334比它更大一点的将是1122343我们会发现我们只需要将右边较大的一个数与前面较小的一个数交换就能变得更大不过为了更小我们需要将交换后的后面部分从小到大排序。
14321从右往前看最右边的1走到4都是升序也就是这一段不可能可以交换变得更大同理只要从右边开始看一直是升序的段就不可能可以交换变得更大而如果出现非升序也就是最左边的1那就必然可以交换了因为一定有右边存在一个数比这个数大当然我们想要最小的更大的数跟最左边的1交换我们就需要找到2。
算法思路 124 2 98765432
从右往左找到一个断层的第一个数如果没有那么整个降序就是答案再给出的例子里是空出来的2在这个断层的数右边找一个比它大但在右边最小的数与其交换。交换后右边的数还是顺序排列的这个更大数是右边的3,交换后变为124398765422反转右边的数注意右边的数一定是按顺序排列的因为我们按1.的方式进行查找的反转后变为124322456789这保证了更大但是是更大中的最小的那一个。
时间复杂度 O ( n ) O(n) O(n) 空间复杂度 O ( 1 ) O(1) O(1)
class Solution {
public:void nextPermutation(vectorint nums) {int i nums.size() - 2;for(; i 0; -- i){if(nums[i] nums[i 1]) break;}if(i 0){reverse(nums.begin(), nums.end());return;}int j i 1;for(; j nums.size(); j){if(nums[i] nums[j]) break;}swap(nums[i], nums[j - 1]);reverse(nums.begin() i 1, nums.end());return;}
};
