首页 > 其他分享 >31. 下一个排列

31. 下一个排列

时间:2024-05-23 14:08:08浏览次数:29  
标签:arr 排列 nums 一个 31 数组 字典

整数数组的一个 排列 就是将其所有成员以序列或线性顺序排列。

例如,arr = [1,2,3] ,以下这些都可以视作 arr 的排列:[1,2,3]、[1,3,2]、[3,1,2]、[2,3,1] 。
整数数组的 下一个排列 是指其整数的下一个字典序更大的排列。更正式地,如果数组的所有排列根据其字典顺序从小到大排列在一个容器中,那么数组的 下一个排列 就是在这个有序容器中排在它后面的那个排列。如果不存在下一个更大的排列,那么这个数组必须重排为字典序最小的排列(即,其元素按升序排列)。

例如,arr = [1,2,3] 的下一个排列是 [1,3,2] 。
类似地,arr = [2,3,1] 的下一个排列是 [3,1,2] 。
而 arr = [3,2,1] 的下一个排列是 [1,2,3] ,因为 [3,2,1] 不存在一个字典序更大的排列。
给你一个整数数组 nums ,找出 nums 的下一个排列。

必须 原地 修改,只允许使用额外常数空间。

示例 1:

输入:nums = [1,2,3]
输出:[1,3,2]
示例 2:

输入:nums = [3,2,1]
输出:[1,2,3]
示例 3:

输入:nums = [1,1,5]
输出:[1,5,1]

class Solution {
public:
    void nextPermutation(vector<int>& nums) {
        int n=nums.size();
        int i=n-2;
        while(i>=0)
        {
            if(nums[i]<nums[i+1])
            {
                break;
            }
            i--;
        }
        if(i>=0)
        {
            int j=n-1;
            while(j>=0)
            {
                if(nums[j]>nums[i])
                {
                    break;
                }
                j--;
            }
            std::swap(nums[i],nums[j]);
        }
        std::reverse(nums.begin()+i+1,nums.end());

    }
};

总的来说,这个算法的思路是:

从后向前找到第一个满足 nums[i] < nums[i+1] 的位置 i。
在 nums[i+1:] 这个子数组中找到一个比 nums[i] 大的最小值 nums[j],并交换 nums[i] 和 nums[j]。
反转 nums[i+1:] 这个子数组,得到下一个排列。

标签:arr,排列,nums,一个,31,数组,字典
From: https://www.cnblogs.com/donghao99/p/18208332

相关文章

  • PureBasic是一种基于BASIC语言的编程语言,它提供了一个简单易用的开发环境,旨在帮助开发
    PureBasic是一种基于BASIC语言的编程语言,它提供了一个简单易用的开发环境,旨在帮助开发人员快速创建跨平台的应用程序。PureBasic的特点如下:简单易学:PureBasic的语法类似于传统的BASIC语言,非常容易学习和理解,适合初学者入门。跨平台支持:PureBasic可以在多个操作系统上运行,包括W......
  • SqlSugar : date绑定到XX失败,可以试着换一个类型,或者使用ORM自定义类型实现
    System.Exception:中文提示:date绑定到Machine失败,可以试着换一个类型,或者使用ORM自定义类型实现EnglishMessage:MachinedatebinderroratSqlSugarEntity(IDataRecord)atSqlSugar.IDataReaderEntityBuilder`1.Build(IDataRecorddataRecord)atSqlSugar.......
  • 写一个Linux的 shell脚本删除目录 stud001~stud140 目录下的所有文件
    用户:在linux的shell脚本中写个循环,可以遍历目录stud001直到stud140,并将目录stud001到stud140目录中的内容全部删除。讯飞星火:在shell脚本中,我们可以使用for循环和rm命令来实现这个需求。以下是一个简单的示例:1#!/bin/bash2foriin$(seq-f"%03g"1140)3do4......
  • 截取第一个字用php生成一个头像
    在做商城时生成随机一个头像,找了一下发现用首个字符直接生成的类也不错,和用第三方外链的话还是有不同的,第三方虽然图片比较多,但是会有超时问题,所以用首字母生成方式本地搞,代码如下:点击查看代码1、方法调用测试letter_avatar("壹零柒")2、生成图片方法functionletter_avata......
  • 推荐一个WPF仪表盘开源控件
    前段时间,做服务器端监控系统,为了界面好看,采用WPF。硬件相关监控,比如CPU、内存等,想用仪表盘控件。网上找了很多这种控件,基本上都是第三方商业控件(虽然很漂亮,不过得money...)。最后在CodeProject上找到了一款还不错的开源的仪表盘控件CircularGauge。用了下该控件,感觉还不错......
  • 记录一个按列内容拆分Excel文件的小方法
    importtkinterastkimportosimporttkinter.filedialogimporttkinter.simpledialogimportpandasaspdimporttkinter.messageboximporttkinter.ttkimporttracebackglobalcolumn,sheet_origlobalcombox_2#按内容分类defsplit_by_group():#获取需......
  • 记录一个批量压缩文件夹的方法
    importosimportzipfilefromtkinterimportfiledialogclassZipDir:"""ZipFile()用于创建1个zip文件对象,示例中的三个参数分别表示:filename:压缩成的zip包的路径(含压缩包名称);例如:xxx.zipmode:可选r,w,a,代表不同的打开文件的方式;r只读;w重写;a添加......
  • 记录一个按文档长度分割Excel文件的方法
    importtkinterastkimportpandasaspdimporttkinter.filedialogimportosimporttracebackwindows=tk.Tk()####按长度拆分——自定义函数##拆分函数defdivision_by_length(iterable,length):iterable_len=len(iterable)start=0while1:......
  • 记录一个批量拆分数据粘贴到各个表里的小脚本
    importosimporttkinterastkimporttkinter.filedialogfromtkinterimportttkimporttkinter.messageboxfromtkinterimportscrolledtextimportxlwingsasxwfrompandasimportExcelFilefrompandasimportread_excelglobaldf_total,cbox_sheet_ori,cbo......
  • 记录一个多对多数据匹配,但是效率不高
    importitertoolsimportosimportpandasaspddefget_result(hope,list_input,used):""":paramhope:#期望相加所得参数:paramlist_input:#所有数值:paramused:#已使用过列表,起始数据为空......