(模拟) 31. 下一个排列——【Leetcode每日一题】

news/2024/4/17 10:05:50

❓ 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]

提示

  • 1 < = n u m s . l e n g t h < = 100 1 <= nums.length <= 100 1<=nums.length<=100
  • 0 < = n u m s [ i ] < = 100 0 <= nums[i] <= 100 0<=nums[i]<=100

💡思路:模拟

首先 从后往前 遍历,找到 第一个 不是倒序的位置:

  • 如果整个数组都是倒序排序,则直接将原数组使用 reverse 函数进行反转成正序即可;
  • 如果找到位置 pp 之后的都是倒序:
    • 再使用二分查找,在 p 之后 的数组内查找到离 nums[p] 最近的较大的数,位置为 q;
    • 然后将 nums[p]nums[q]互换,互换完 p 之后的仍是倒序;
    • 再将在 p 之后 的数组 使用 reverse 函数进行反转成正序即可。

🍁代码:(C++、Java)

C++

class Solution {
private:int findp(vector<int>& nums, int left, int right, int& target){//二分查找,找到离target最近的较大数while(left <= right){int mid = left + (right - left) / 2;if(nums[mid] <= target) right = mid - 1;else  left = mid + 1;}return right;}
public:void nextPermutation(vector<int>& nums) {int n = nums.size();if(n < 2) return;int p = n - 2;while(p >= 0){//从后往前找到第一个不是递减的位置if(nums[p] >= nums[p + 1]) {p--;continue;}else break;}if(p == -1){reverse(nums.begin(), nums.end());return;}int q = findp(nums, p + 1, n - 1, nums[p]);int tmp = nums[p];nums[p] = nums[q];nums[q] = tmp;reverse(nums.begin() + (p + 1), nums.end());return;}
};

Java

class Solution {private int findp(int[] nums, int left, int right, int target){//二分查找,找到离target最近的较大数while(left <= right){int mid = left + (right - left) / 2;if(nums[mid] <= target) right = mid - 1;else  left = mid + 1;}return right;}private void reverse(int[] nums, int start) {//反转int left = start, right = nums.length - 1;while (left < right) {int tmp = nums[left];nums[left++] = nums[right];nums[right--] = tmp;}}public void nextPermutation(int[] nums) {int n = nums.length;if(n < 2) return;int p = n - 2;while(p >= 0){//从后往前找到第一个不是递减的位置if(nums[p] >= nums[p + 1]) {p--;continue;}else break;}if(p == -1){reverse(nums, 0);return;}int q = findp(nums, p + 1, n - 1, nums[p]);int tmp = nums[p];nums[p] = nums[q];nums[q] = tmp;reverse(nums, p + 1);return;}
}

🚀 运行结果:

在这里插入图片描述

🕔 复杂度分析:

  • 时间复杂度 O ( n ) O(n) O(n),其中 n 为数组的长度。
  • 空间复杂度 O ( 1 ) O(1) O(1),只需要常数的空间存放若干变量。

题目来源:力扣。

放弃一件事很容易,每天能坚持一件事一定很酷,一起每日一题吧!
关注我LeetCode主页 / CSDN—力扣专栏,每日更新!

注: 如有不足,欢迎指正!


http://www.ppmy.cn/news/708875.html

相关文章

15.4 寸macbook pro

MC976LL/A $2,699.99 2.7G, 16G 768G HD 4000GT 650M Retina 屏 MC976CH/A 19999 元 2.6G, 8G 512G HD 4000GT 650M Retina 屏 ME665LL/A $2,599.99 2.7G 16G 512G HD 4000GT 650M Retina 屏 bestbuy (15911.94元) ME665CH/A 20988 元 2.7G 16G 512G HD 4000G…

ME51n,ME52n,ME53n屏幕增强

使用增强&#xff1a;MEREQ001 购买申请中的客户自有数据 1、如果需要向PR中加入自定义字段&#xff0c;事务码se11&#xff0c;打开透明表EBAN&#xff0c;双击include&#xff1a;CI_EBANDB&#xff0c;创建结构CI_EBANDB&#xff0c;维护自定义的字段。 2、事务码CMOD cr…

数字化转型|银行业数据中心数字化转型之模型篇 03

导语&#xff1a; 银行业数据中心数字化转型是一项系统性工程既涉及管理层面转型——包括数字化转型战略、基础架构和技术架构转型、技术创新和知识体系转型&#xff0c;又涉及执行层面转型——包括人员管理&#xff08;P&#xff09;、流程管理&#xff08;P&#xff09;、技…

Java面试题及答案整理( 金九银十最新版,持续更新)

最近可能有点闲的慌&#xff0c;没事就去找面试面经&#xff0c;整理了一波面试题。我大概是分成了 Java 基础、中级、高级&#xff0c;分布式&#xff0c;Spring 架构&#xff0c;多线程&#xff0c;网络&#xff0c;MySQL&#xff0c;Redis 缓存&#xff0c;JVM 相关&#xf…

Java、C#、Oracle和VB6中常用的通配符和模式匹配方式的详细说明和示例

当涉及到通配符和模式匹配时&#xff0c;以下是Java、C#、Oracle和VB6中常用的通配符和模式匹配方式的详细说明和示例&#xff1a; Java 通配符和模式匹配&#xff1a; “*”&#xff08;星号&#xff09;通配符&#xff1a; "*"表示匹配零个或多个字符。示例&#x…

小米平板开启位置服务器,小米平板电脑防盗定位方法

您可能感兴趣的话题&#xff1a; 小米 核心提示&#xff1a;小米平板并没有内置GPS模块&#xff0c;因此理论上是不能定位的。不过在网上发现有网友给出了一些其他的办法&#xff0c;同样可以实现小米平板电脑定位&#xff0c;并且方法还少&#xff0c;网友共罗列了三种小米平板…

小米摄像头修改wifi

为了安全&#xff0c;wifi应该定期更换密码。 麻烦的事情来了&#xff0c;wifi密码更换后&#xff0c;小米摄像头没有内置修改wifi的功能。唯一的方法是重置。 重置步骤如下&#xff1a; 1.准备工作 确认米家app可用&#xff0c;wifi密码修改并记下新密码。 将原来添加的摄…

小米9刷面具和模块

准备工作: 没解BL锁的需要先解锁 1.按住音量键下和关机键进入Fastboot模式连接电脑 2.这里使用奇兔刷机连接手机,中途会自动安装驱动,若安装驱动失败可使用驱动精灵或驱动人生手动安装驱动.安装完驱动后奇兔刷机会显示已经连接到手机 开启root: 1.下载twrp https://twr…

什么软件可以测试小米手机电池,小米10使用9个月电池测试

小米10使用9个月电池测试 2021-03-28 19:56:48 51点赞 70收藏 180评论 先说结论&#xff1a;小米10使用9个月&#xff0c;健康值为62%&#xff0c;属于重度手机用户。 过年后&#xff0c;明显感觉电池不耐用&#xff0c;出门半天都有续航焦虑&#xff0c;下面有图为证&#xff…

小米6android9原生rom,小米6 安卓10 原生体验 LineageOS17.1 流畅 ROOT

介绍 ROM为第三方编译安卓10 LineageOS17.1 &#xff0c;基本功能正常&#xff0c;如有其他bug&#xff0c;理性对待 使用Magisk ROOT授权 刷机完成后请务必到设置中手动设置当前系统时间和时区 去网络图标上面的感叹号和x号方法&#xff1a;打开CaptiveMgr软件--自动弹出授权弹…

小米8 android9手势,数码教程资讯:小米9怎么开启全面屏手势

现在各种各样的数码设备在我们的生活当中几乎可以说是无处不在&#xff0c;平时我们使用的手机&#xff0c;IP&#xff0c;电脑等等这些都属于数码设备&#xff0c;那么这些数码设备当中会存在着很多的功能&#xff0c;当然在我们使用的过程当中自然也会出现说各种的问题&#…

slab 内存池的设计与实现

目录 从一个简单的内存页开始聊 slab slab 的总体架构设计 slab 的组织架构 ​编辑 ​编辑 参考文献 伙伴系统内存分配原理的相关内容来看&#xff0c;伙伴系统管理物理内存的最小单位是物理内存页 page。也就是说&#xff0c;当我们向伙伴系统申请内存时&#xff0c;至少…

leetcode消失的数字

题目描述 数组 nums 包含从 0 到 n 的所有整数&#xff0c;但其中缺了一个。请编写代码找出那个缺失的整数。你有办法在 O ( n ) O(n) O(n) 时间内完成吗&#xff1f; 示例 1&#xff1a; 输入&#xff1a;[3,0,1] 输出&#xff1a;2 leetcode链接&#xff1a;消失的数字 ⭕…

神(gai)奇(si)的MIUI优化

版本 MIUI 8 7.3.2|开发版 问题描述 Installation failed with message Failed to establish session 解决方案 设置 -> 更多设置 -> 开发者选项 -> 启用MUUI优化看到右边按钮没有, 把这该死的功能关掉 重启你的手机, 你会发现问题解决掉了 谨献给所有使用小米手…

复盘红米手机慢问题,针对小米手机 miui系统优化设置,实测红米note8,和k20 pro可行,流畅度起码提升了20%,能马上感觉到。

复盘开始&#xff1a; 1.9月14号&#xff0c;我的k20 屏幕碎了&#xff0c;于是乎我在闲鱼上以850买了用了一年的k20&#xff0c;再在闲鱼上花了600买了个红米Note8&#xff08;那哥们是才买的&#xff0c;不喜欢所以买了&#xff09;&#xff0c;打算先用一段时间&#xff0c…

Android性能优化系列篇(一):UI优化

前言 汇总了一下众多大佬的性能优化文章&#xff0c;本期汇总一下安卓性能优化部分的知识点&#xff0c;主要包含&#xff1a; UI优化/启动优化/崩溃优化/卡顿优化/安全性优化/弱网优化/APP深度优化等等等~ 本篇是第一篇&#xff1a;UI优化&#xff01; [非商业用途,如有侵权,…

记一次小米MIUI优化未启用,导致页面没有正常显示的坑

在公司一个app产品上挂了H5链接&#xff0c;其他手机登录账号点击进去正常&#xff0c;客户反馈小米10至尊小米11点击进去提示错误信息。自己用同事的小米11又能正常显示首页&#xff0c;给人整懵了&#xff0c;然后另外一个同事提供了从MIUI优化去找问题的思路https://www.jia…

miui android系统更新日志,MIUI再升级,更新了Android 11系统,优化了1项内容

原标题&#xff1a;MIUI再升级&#xff0c;更新了Android 11系统&#xff0c;优化了1项内容 目前小米MIUI系统又迎来了更新&#xff0c;本次更新除了优化了新功能&#xff0c;最大的亮点就是Redmi K30 Pro手机适配了很久的基于Android 11系统的MIUI 12系统总算发布了&#xff0…

Android性能优化之页面优化

前言&#xff1a; 1.现在网上有很多讲如何进行界面性能优化的文章&#xff0c;但是往往就讲到了如何解决内存波动问题。两者虽然有关联性&#xff0c;但是并不能完全划等号的&#xff0c;内存波动确实一定程度上会影响界面的绘制&#xff0c;但是也只是其中一种原因&#xff0…

root除miui广告,miui11去除广告

小米MIUI广告怎么关闭 MIUI广告关闭教程 MIUI现在广告越来越多引来众多吐槽&#xff0c;很多米粉还不知道MIUI广告怎么关闭&#xff0c;下面安下小编特意整理了MIUI广告关闭方法大全&#xff0c;还你一个纯净清爽的MIUI。 MIUI广告怎么关闭&#xff1f; 下面一一介绍下MIUI各…
最新文章