力扣LeetCode 31.下一个排列

整数数组的一个排列就是将其所有成员以序列或线性顺序排列。例如arr [1,2,3]以下这些都可以视作arr的排列[1,2,3]、[1,3,2]、[3,1,2]、[2,3,1]。整数数组的下一个排列是指其整数的下一个字典序更大的排列。更正式地如果数组的所有排列根据其字典顺序从小到大排列在一个容器中那么数组的下一个排列就是在这个有序容器中排在它后面的那个排列。如果不存在下一个更大的排列那么这个数组必须重排为字典序最小的排列即其元素按升序排列。例如arr [1,2,3]的下一个排列是[1,3,2]。类似地arr [2,3,1]的下一个排列是[3,1,2]。而arr [3,2,1]的下一个排列是[1,2,3]因为[3,2,1]不存在一个字典序更大的排列。给你一个整数数组nums找出nums的下一个排列。必须原地修改只允许使用额外常数空间。示例 1输入nums [1,2,3]输出[1,3,2]示例 2输入nums [3,2,1]输出[1,2,3]示例 3输入nums [1,1,5]输出[1,5,1]提示1 nums.length 1000 nums[i] 100解题思路因为我们要找正好字典序比现有数组大一点的数组那我们就要保证数组前面尽量不动。就从后往前找升序排序中下降的那个数将它用后面正好比它大的数替换之后再将后面原本的升序改为降序即从前往后看的降序改为升序即可。如果遇到最大字典序则也可以这么做它会将整个数组的顺序相反。class Solution { public: void nextPermutation(vectorint nums) { int i; for(inums.size()-1;i0;i--) { if(nums[i-1]nums[i]) { continue; } for(int jnums.size()-1;ji;j--) { if(nums[j]nums[i-1]) { continue; } int tmpnums[j]; nums[j]nums[i-1]; nums[i-1]tmp; break; } break; } sort(nums.begin()i,nums.end()); } };