leetcode 31. Next Permutation

拼搏现实的明天。 2022-07-28 08:45 98阅读 0赞

Implement next permutation, which rearranges numbers into the lexicographically next greater permutation of numbers.

If such arrangement is not possible, it must rearrange it as the lowest possible order (ie, sorted in ascending order).

The replacement must be in-place, do not allocate extra memory.

Here are some examples. Inputs are in the left-hand column and its corresponding outputs are in the right-hand column.  
`1,2,3` → `1,3,2`  
`3,2,1` → `1,2,3`  
`1,1,5` → `1,5,1`

class Solution {
    public:
    	void nextPermutation(vector<int>& nums) {
    		if (nums.size() < 2)
    			return ;
    		
    		vector<int>aa = nums;
    		sort(aa.begin(), aa.end());
    		int k = nums.size()-1;
    		while (k >= 1)
    		{
    			vector<int>cc; cc.push_back(nums[k]);
    			while (k >= 1 && nums[k] <= nums[k - 1])
    			{
    				cc.push_back(nums[k - 1]);
    				k--;
    			}
    			
    			if (k == 0)
    			{
    				nums = aa;
    				return;
    			}
    			cc.push_back(nums[k - 1]);
    			sort(cc.begin(), cc.end());
    			for (int i = 0; i < cc.size();i++)
    				if (cc[i] > nums[k - 1])
    				{
    					nums[k - 1] = cc[i];
    					cc.erase(cc.begin() + i, cc.begin() + i + 1);
    					for (int j = 0; j < cc.size(); j++)
    						nums[k + j] = cc[j];
    					return;
    				}
    		}
    	}
    };

accepted

发表评论取消回复

表情：

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

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

相关阅读

相关 Next Permutation--LeetCode

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

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

相关 leetcode 31. Next Permutation

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

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

相关【LeetCode】31. Next Permutation解法

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

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

相关 [leetcode javascript解题]Next Permutation

leetcode 第31题 “Next Permutation”描述如下，有点长： > Implement next permutation, which rearrange

我会带着你远行/ 2022年07月13日 03:59/ 0 赞/ 112 阅读

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

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

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

相关 leetcode 31. Next Permutation

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

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

相关 Next Permutation

题目 Implement next permutation, which rearranges numbers into the lexicographically ne

左手的ㄟ右手/ 2022年06月06日 04:42/ 0 赞/ 132 阅读

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

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

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

相关 #31 Next Permutation———Top 100 Liked Questions

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

超、凢脫俗/ 2022年04月25日 06:30/ 0 赞/ 94 阅读

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

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

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