class Solution {
public:
void nextPermutation(vector<int>&nums) {
int len = nums.size();
int k = -, l = , i = ;//注意三个变量的初始化值 for (i = len - /*即倒数第二个元素(逆序遍历)*/;i >= ;--i)
if (nums[i + ] > nums[i]) {
k = i;
break;//因为是逆序,故此时得到的k一定是最大的
} if (k == -) {
reverse(nums.begin(), nums.end());//此时代表原数组为逆序排列,故直接反转
return;
} //接下来找i
for (i = len - ;i >= ;--i) {
if (nums[i] > nums[k]) {
l = i;
break;
}
} //二者交换
swap(nums[k], nums[l]); //再反转k之后的元素(不包括nums[k])
reverse(nums.begin() + k + , nums.end());
}
};
补充一个非常复杂,不美观的版本,使用python实现,也可以AC,能写出来我也挺佩服自己的。
这个版本的主要思想就是从后向前找,记录已查找范围的最大值,当查找到一个值a比已查找区域的最大值maxnum要小的时候,就可以进行换位操作了。
但是要确定一个在已查找区域中比a值大的最小的那个值来进行交换。所以这段代码写的不太美观,如果有高级一点的api可能更美观一些吧。
class Solution:
def nextPermutation(self, nums: 'List[int]') -> 'None':
for i in range(len(nums)-1,-1,-1):
basenum = nums[i]
maxnum = basenum
for j in range(i-1,-1,-1):
curnum = nums[j]
maxnum = max(maxnum,curnum)
if curnum < maxnum:
for x in sorted(nums[j:]):
if x > curnum:
z = j - 1
for y in nums[j:]:
z += 1
if x == y:
slices1 = nums[j:z]
slices2 = nums[z+1:]
slices1.extend(slices2)
nums[j] = nums[z]
nums[j+1:]=sorted(slices1)
return nums.sort()