返回数组下一个排列的代码不准确

Question

我正在解决一个关于leetcode的问题，描述:

整数数组的下一个排列是该整数在字典顺序上的下一个更大的排列。更正式地说，如果数组的所有排列都按照字典顺序在一个容器中排序，那么该数组的下一个排列就是在排序后的容器中紧随其后的排列。如果不能进行这样的排列，则必须按照尽可能低的顺序重新排列数组(即按升序排序)。

这是我想出了在c++中:

void nextPermutation(vector<int>& nums) {

int index = -1, j = nums.size() - 1;
for (int i = nums.size() - 1; i > 0; i--)
{
if(nums[i - 1] < nums[i])
{
index = i - 1;
break;
}
}
if(index == -1)
{
reverse(nums.begin(), nums.end());
return;
}
for (int i = nums.size() - 1; i >= index + 1; i--)
{
if(nums[i] > nums[index])
{
j = i;
}
break;
}
swap(nums[index], nums[j]);
reverse(nums.begin() + index + 1, nums.end());
}

在这里，我从左到右遍历数组，寻找一个比它右边的元素小的元素(命名为index)，然后再次遍历它，寻找一个比它前面的数字大的数字，交换它们，然后在index

之后反转数组此代码适用于示例情况，但在以下情况下失败:

输入:[2、3、1]

MyOutput:(1、2、3)

预期输出:[3 1 2]

我不明白我做错了什么，一切都应该工作，但它不是。

Answer 1

您的问题是第二个循环中的break语句在if块之外。

if (nums[i] > nums[index])
{
j = i;
}
break;    // <--------- this should be inside if

放进去，得到正确的结果。

if (nums[i] > nums[index])
{
j = i;
break;
}

演示:https://godbolt.org/z/147We9c4q