例子：
Input -> output 1,2,3 → 1,3,2 3,2,1 → 1,2,3 1,1,5 → 1,5,1
问题说明：
给定一个数字，使用数组中给出的相同数字查找下一个最高数字。
例如：
1234 -> 1243
1235无效，因为数字“ 5”不在输入数组中。因此，第二高的数字将是“ 1243”。
另一个例子：
4132 -> 4213
还可以，最后一个：
4321-> none.
由于数字已经按降序排序，因此无法找到下一个更高的元素。
此问题可以通过3种方式解决。
- 蛮力法
- 直接解决方案
- 使用内置功能。 [不是一个真正的解决方案，很高兴知道]
我们将研究以下所有3个解决方案。
1.暴力手段。
解决方案很简单。
我们将数字加1并检查给定数组中是否存在所有数字。
如果考虑了所有数字，我们将使用该数字，否则我们将再次搜索。
显然，这将花费很多时间。首先，您可以提供此解决方案，如果面试官不满意，请转到步骤2nd 解。
2.直接解决方案
在这种方法中，我们采用2个指针。
第1步： 在给定的数组的右侧，找到一个不按升序排列的数字。将该数字标记为num_1。
第2步： 然后，我们从num_1的右边找到另一个数字，以使其是最小的数字，但大于num_1，并将其标记为num_2。
第三步： 交换num_1，num_2。
步骤4： 从num_1的原始位置的右边对数字进行排序。
我们将借助一个示例来分析上述步骤：
给定数组：
3 2 8 4 1
从步骤1开始，从右侧搜索“ 2”正在打破“ 1 4 8”的升序。将其标记为num_1。
从步骤2：“ 4”是大于num_1的最小数字。将其标记为num_2。
从步骤3：交换num_1和num_2
从第4步开始：从num_1的原始位置开始按升序对数组进行排序。
我们将获得期望的结果。
解决方案3：使用库函数：
使用C ++中STL中的“ next_permutation（）”函数。
C ++解决方案
/*
* File : Next_Permutation.cpp
*/
#include<iostream>
#include<vector>
using namespace std;
void next_permutation_using_direct_approach(vector<int>& nums)
{
int len = nums.size();
int num_1_index;
int num_2_index;
//step 1: find the index of num 1 so that it is not in ascending order
for (num_1_index = len - 2; num_1_index >= 0; num_1_index--)
{
if (nums[num_1_index] < nums[num_1_index + 1])
{
break;
}
}
//if we did not find, we just reverse the numbers.
// example: if the number is 123, then 321 will be the next heighest permutation
if (num_1_index < 0)
{
reverse(nums.begin(), nums.end());
}
else
{
//step 2, we find second number index, such that it is greater than num 1
for (num_2_index = len - 1; num_2_index > num_1_index; num_2_index--)
{
//if we find, break the loop
if (nums[num_2_index] > nums[num_1_index])
{
break;
}
}
// step 3: swap the numbers
swap(nums[num_1_index], nums[num_2_index]);
//step 4: reverse the numbers
reverse(nums.begin() + num_1_index + 1, nums.end());
}
}
void nextPermutation_using_library_function(vector<int>& nums)
{
next_permutation(begin(nums), end(nums));
}
int main()
{
vector<int> number;
number.push_back(3);
number.push_back(2);
number.push_back(8);
number.push_back(4);
number.push_back(1);
for (int i = 0; i < number.size(); i++)
{
cout <<number[i] << " ";
}
cout<<endl;
//nextPermutation_using_library_function (number);
next_permutation_using_direct_approach (number);
for (int i = 0; i < number.size(); i++)
{
cout <<number[i] << " ";
}
cout<<endl;
}
输出量
3 2 8 4 1 3 4 1 2 8
该网站上可用的教程列表：
| C编程20+章 | C ++编程80+章 |
| 100多个编码问题 | 数据结构和算法85+章 |
| 系统设计20+章 | Shell脚本编写12章 |
| 4g LTE 60+章节 | 最常见的编码问题 |
| 5G NR 50+章 | Linux系统编程20+章 |
