下一个排列(数组推导）

2021-06-05 21:04

阅读：417

标签：als 使用 oid str 实现代码实现 pre ext 输入

题目描述

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

示例 1：

输入：nums = [1,2,3]

输出：[1,3,2]

示例 2：

输入：nums = [3,2,1]

输出：[1,2,3]

示例 3：

输入：nums = [1,1,5]

输出：[1,5,1]

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

解题思路

1.首先数组中从后往前寻找，升序排列的第一个位置i,使得nums[i]

2.在[1+1,n]中寻找一个最小的输nums[j]使得nums[j]大于nums[i]

3.交换nums[i]与nums[j]的位置，然后翻转子数组[i+1,n]

代码实现

class Solution {
public:
    void nextPermutation(vectorint>& nums) {
        bool isFind = false;
        int n = nums.size();
        int i = n - 2;
        //寻找升序排列的第一个位置i,使得nums[i] for(; i >= 0; i--){
            if(nums[i] 1]){
                isFind = true;
                break;
            }
                
        } 
        //在[1+1,n]中寻找一个最小的输nums[j]使得nums[j]大于nums[i]
        if(isFind){
            int k = i + 1;
            for(int j = i + 1; j ){
                if(nums[j] > nums[i] && nums[j]  nums[k]){
                        k = j;
                }
            }  
            swap(nums[i], nums[k]); 
        }
        else{
            i = -1;
        }   
        //翻转子数组[i+1,n]    
        int mid = (n - i)/2;
        for(int k = 1; k ){
            swap(nums[i + k], nums[n - k]);
        }
    }
};

下一个排列(数组推导）

标签：als 使用 oid str 实现代码实现 pre ext 输入

原文地址：https://www.cnblogs.com/latencytime/p/14620039.html

上一篇：Java入门之04-Java方法

下一篇：java反射和动态代理实现与原理详细分析

文章来自：搜素材网的编程语言模块，转载请注明文章出处。
文章标题：下一个排列(数组推导）
文章链接：http://soscw.com/essay/90978.html

亲，登录后才可以留言！

下一个排列(数组推导）

评论

热门文章

推荐文章

最新文章

置顶文章