31下一个排列

一、前言

标签：其他。

问题来源LeetCode 31 难度：中等。

问题链接：https://leetcode-cn.com/problems/next-permutation/

二、题目

实现获取下一个排列的函数，算法需要将给定数字序列重新排列成字典序中下一个更大的排列。如果不存在下一个更大的排列，则将数字重新排列成最小的排列（即升序排列）。必须原地修改，只允许使用额外常数空间。

以下是一些例子，输入位于左侧列，其相应输出位于右侧列。
1,2,3 → 1,3,2
3,2,1 → 1,2,3
1,1,5 → 1,5,1

三、思路

从右边找到第一对两个连续的数字 a[i] 和 a[i+1]，它们满足 a[i] < a[i+1]。在[i+1,n]中从后往前找第一个大于a[i]的数a[pos]，将a[i]和a[pos]互换。因此，[i+1,n]是降序排序，将其调整为升序即可。

例如：5、3、7、6、1

1. 从后往前查找，第一个满足 a[i] > a[i−1]， i = 1
2. 从后往前查找a[2,4]中第一个大于a[1]的是a[3]，互换a[1]和a[3]，此时数组：5，6，7，3，1
3. 将a[2,4]右降序调整为升序，调整之后数组：5，6，1，3，7
4. 结果：5，6，1，3，7

四、编码实现

//==========================================================================
/*
* @file    : 031_NextPermutation.h
* @label   : 其他
* @blogs   : https://blog.csdn.net/nie2314550441/article/details/107587953
* @author  : niebingyu
* @date    : 2020/07/25
* @title   : 31.下一个排列
* @purpose : 实现获取下一个排列的函数，算法需要将给定数字序列重新排列成字典序中下一个更大的排列。
* 如果不存在下一个更大的排列，则将数字重新排列成最小的排列（即升序排列）。
* 必须原地修改，只允许使用额外常数空间。
*
* 以下是一些例子，输入位于左侧列，其相应输出位于右侧列。
*   1,2,3 → 1,3,2
*   3,2,1 → 1,2,3
*   1,1,5 → 1,5,1
*
*
* 来源：力扣（LeetCode）
* 难度：中等
* 链接：https://leetcode-cn.com/problems/next-permutation/
*/
//==========================================================================
#pragma once
#include <iostream>
#include <vector>
#include <algorithm>
#include <assert.h>
using namespace std;

#define NAMESPACE_NEXTPERMUTATION namespace NAME_NEXTPERMUTATION {
#define NAMESPACE_NEXTPERMUTATIONEND }
NAMESPACE_NEXTPERMUTATION

class Solution 
{
public:
    void nextPermutation(vector<int>& nums) 
    {
        if(nums.size() <= 1) return;
        int pos = nums.size() - 1, start = 0;
        for(start = nums.size() - 2; start >= 0; --start)
        {
            if(nums[start] < nums[start + 1])
            {
                while(nums[start] >= nums[pos]) pos--;
                swap(nums[start],nums[pos]);
                break;
            }
        }

        reverse(nums.begin() + 1 + start, nums.end());
        return;
    }
};

以下为测试代码//
// 测试 用例 START
void test(const char* testName, vector<int>& nums, vector<int> expect)
{
    Solution s;
    s.nextPermutation(nums);

    if (nums == expect)
        cout << testName << ", solution passed." << endl;
    else
        cout << testName << ", solution failed. " << endl;
}

// 测试用例
void Test1()
{
    vector<int> nums = { 1,2,3 };
    vector<int> expect = { 1,3,2 };
    test("Test1()", nums, expect);
}

void Test2()
{
    vector<int> nums = { 3,2,1 };
    vector<int> expect = { 1,2,3 };
    test("Test2()", nums, expect);
}

void Test3()
{
    vector<int> nums = { 1,1,5 };
    vector<int> expect = { 1,5,1 };
    test("Test3()", nums, expect);
}

NAMESPACE_NEXTPERMUTATIONEND
// 测试 用例 END
//
void NextPermutation_Test()
{
    cout << "------ start 31.下一个排列 ------" << endl;
    NAME_NEXTPERMUTATION::Test1();
    NAME_NEXTPERMUTATION::Test2();
    NAME_NEXTPERMUTATION::Test3();
    cout << "------ end 31.下一个排列 --------" << endl;
}

执行结果：