leetcode 31下一个更大的数字next permutation

逃离我推掉我的手 2023-03-03 06:30 14阅读 0赞

题目：  
给一个数组，按照排序，给出下一个更大的组合顺序，如果当年是最大的数字，那么给出最小的数字。

思路：  
要使得这个数字比当前更大，那就得从后面往前找到第一个往下减少得位，然后再从这个之后找到第一个大于这个target得数，交换，然后再逆序（因为寻找的时候就是以从后往前递增 ，交换后还是递增，为了保证greater，所以要逆序（从target之后）

代码：

class Solution { 
    public:
        void nextPermutation(vector<int>& nums) { 
            //next_permutation(begin(nums), end(nums));
            if(nums.size()<=1)
                return ;
            int n=nums.size(),k;
            for(k=n-2; k>=0; k--){ 	//从后往前找到第一个下降得
                if(nums[k]< nums[k+1])
                    break;
            }
            if(k<0){ 		//排除全部是从后往前递增的。直接reverse就可
                reverse(nums.begin(),nums.end());
                return ;
            }
            else{ 	//从后往前找到第一个大于的，然后swap，再逆序
                int right=n-1;
                for(; right>k; right--){ 
                    if(nums[right]>nums[k])
                        break;
                }
                swap(nums[right], nums[k]);
                reverse(nums.begin()+k+1, nums.end());
                return ;
            }
            return ;
        }
    };

发表评论取消回复

表情：

评论列表（有 0 条评论，14人围观）

还没有评论，来说两句吧...

相关阅读

相关 leetcode 31下一个更大的数字next permutation

题目：给一个数组，按照排序，给出下一个更大的组合顺序，如果当年是最大的数字，那么给出最小的数字。思路：要使得这个数字比当前更大，那就得从后面往前找到第一个往下减

逃离我推掉我的手/ 2023年03月03日 06:30/ 0 赞/ 15 阅读

相关 Next Permutation（C++下一个排列）

(1) 模拟法 class Solution { public: void nextPermutation(vector<int>& n

迈不过友情╰/ 2022年10月09日 12:17/ 0 赞/ 122 阅读

相关 Next Permutation--LeetCode

mplement next permutation, which rearranges numbers into the lexicographically next grea

淩亂°似流年/ 2022年08月07日 13:41/ 0 赞/ 174 阅读

相关 leetcode 31. Next Permutation

Implement next permutation, which rearranges numbers into the lexicographically next gre

拼搏现实的明天。/ 2022年07月28日 08:45/ 0 赞/ 146 阅读

相关【LeetCode】31. Next Permutation解法

31. Next Permutation Implement next permutation, which rearranges numbers into t

深藏阁楼爱情的钟/ 2022年07月28日 05:21/ 0 赞/ 149 阅读

相关怎样找下一个序列: next_permutation

有一序列 1 6 3 5 4 2 end (其中最后一个数后面的一个数记为end) 他的字典序的下一个排列会是什么呢? 1. 我们可以从后往前找到第一个降序对(x, y),

本是古典何须时尚/ 2022年07月11日 13:48/ 0 赞/ 44 阅读

相关 [Leetcode][python]Next Permutation/下一个排列

题目大意寻找一组数排序的下一个序列例如：1，2，3，下一个就是1，3，2 解题思路官方思路（与下方相同）：[https://leetcode-cn.co

╰半夏微凉°/ 2022年06月09日 13:46/ 0 赞/ 214 阅读

相关 leetcode 31. Next Permutation

Implement next permutation, which rearranges numbers into the lexicographically next gre

Bertha 。/ 2022年06月09日 09:40/ 0 赞/ 146 阅读

相关 LeetCode 31.Next Permutation (下一个排列)

题目描述：实现获取下一个排列的函数，算法需要将给定数字序列重新排列成字典序中下一个更大的排列。如果不存在下一个更大的排列，则将数字重新排列成最小的排列（即升序排列）。

约定不等于承诺〃/ 2022年05月11日 04:04/ 0 赞/ 193 阅读

相关 31. Next Permutation【下一个排列】

Implement next permutation, which rearranges numbers into the lexicographically next gre

﹏ヽ暗。殇╰゛Y/ 2022年04月23日 06:24/ 0 赞/ 165 阅读