美文网首页
31. Next Permutation

31. Next Permutation

作者: jecyhw | 来源:发表于2019-05-22 11:00 被阅读0次

    题目链接

    https://leetcode.com/problems/next-permutation/

    解题思路

    拿一个例子来说明,如下:

    7, 5, 1, 2, 6, 3, 0

    1. 从后往前找第一个相邻两个元素后一个元素大于前一个元素,也就是2和6
    2. 在2后面也是从右往前周第一个大于2的数,也就是3
    3. 交换2和3

    7, 5, 1, 3, 6, 2, 0

    1. 对3后面的数转置一下,就可以得到答案

    7, 5, 1, 3, 0, 2, 6

    在第1步找到的2和6,2之后的数肯定是降排,在第2和3步之后,3后面的数仍然满足降排性质,所有在对3后面的数进行转置得到一个升排就是答案。

    代码

    class Solution {
    public:
        void nextPermutation(vector<int>& nums) {
            if (nums.size() < 2) {
                return;
            }
    
            //从后往前找第一个符合nums[i] > nums[i - 1]
            for (int i = nums.size() - 1; i > 0 ; i--) {
                if (nums[i] > nums[i - 1]) {
                    //在nums[i - 1]之后找比nums[i - 1]大且最小的数进行交换
                    for (int k = nums.size() - 1; k >= i ; --k) {
                        if (nums[k] > nums[i - 1]) {
                            swap(nums[i - 1], nums[k]);
                            break;
                        }
                    }
    
                    //转置下
                    reverse(nums.begin() + i, nums.end());
                    return;
                }
            }
            reverse(nums.begin(), nums.end());
        }
    };
    
    

    相关文章

      网友评论

          本文标题:31. Next Permutation

          本文链接:https://www.haomeiwen.com/subject/efryzqtx.html