LeetCode刷题之31.下一个排列

文章目录

  • 1. 题目
  • 2.分析
  • 3.解答
    • 3.1 先排序,后交换
    • 3.2 先交换,后排序

1. 题目

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

  • 例如,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 的下一个排列。

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

2.分析

这里需要找下一个字典序更大的排列,那么意味着要从数组的后端入手。如果最后两个元素原本就是升序的,那么就直接交换这两个元素就好了,这个组合即使下一个更大的组合。在这里插入图片描述
但是,如果这两个元素不是升序的,那么交换这两个元素反而导致拍列更小。因此,必须要找到从后向前数的第一个升序排列的两个相邻元素。找到之后,交换这两个元素即可。
请添加图片描述
但是,交换后的元素依然不一定是下一个更大排列组合。如[5,7,6,4]这个排列,交换5和7,得到的是[7,5,6,4]这个组合,显然不是下一个更大排列,毕竟手动排列组合一下,发现下一个组合应该是[6,4,5,7]
请添加图片描述

那么,应该是考虑从后向前第一个升序段的后一个元素开始,将后面所有的元素按字典排序,然后找到紧挨着升序点前一个元素的那个元素,将其交换即可。
或者找到紧挨着升序段前一个元素的数据,将其进行交换,然后将从升序段后一个元素开始的数据,按字典方式排序。

3.解答

3.1 先排序,后交换

public class Solution {
	public void nextPermutation(int[] nums) {
        if (nums.length <= 1) return;
        int len = nums.length;

        for (int i = len - 1; i > 0;i--) {
            if (nums[i] > nums[i - 1]) {
                Arrays.sort(nums, i, len);

                for (int j = i; j < len; j++) {
                    if (nums[j] > nums[i - 1]) {
                        int temp = nums[j];
                        nums[j] = nums[i - 1];
                        nums[i - 1] = temp;
                        return;
                    }
                }
            }
        }

        Arrays.sort(nums);
        }
}

3.2 先交换,后排序

public class Soultion {
	public void nextPermutation(int[] nums) {
		if (nums.length <= 1) return;
		int i = nums.length - 2;
		int j = nums.length - 1;
		int k = nums.length - 1;
		
		while (i >= 0 && nums[i] >= nums[j]) {
			i--;
			j--;
		} 

		if (i >= 0) {
			while (nums[i] > num[k]) {
				k--;
			}
			swap(nums, i, k);
		}
		
		Arrays.sort(nums, j, nums.length);
	}
	
	private void swap(int[], int i, int k) {
		int temp = nums[i];
		nums[i] = nums[k];
		nums[k] = temp;
	}
}

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/521376.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

睿考网:注册会计师科目搭配技巧

注册会计师考试共考六门&#xff0c;关于考试科目的具体搭配&#xff0c;考生可以根据自己的学习情况来进行合理搭配&#xff0c;睿考网为大家推荐常见的科目搭配&#xff1a; 报两科&#xff1a; 1. 《会计》《税法》 2. 《会计》《审计》 3. 《财务成本管理》《公司战略与…

如何从数码相机恢复已删除的照片?

“嗨&#xff0c;我删除了索尼数码相机中的所有照片。有什么办法可以让他们回来吗&#xff1f;” ——刘凯 我们经常从数码相机中删除照片。但是&#xff0c;如果我们误删除了一些重要的照片&#xff0c;则很难将其恢复&#xff0c;因为删除的照片可能会绕过回收站或垃圾箱&am…

SQL语句的编写

##创建用户-建表建库 #创建一个用户名为 feng&#xff0c;允许从任何主机 % 连接&#xff0c;并使用密码 sc123456 进行身份验证的用户。 rootTENNIS 16:33 scmysql>create user feng% identified by sc123456; Query OK, 0 rows affected (0.04 sec) #创建一个名为fen…

Golang | Leetcode Golang题解之第12题整数转罗马数字

题解&#xff1a; 题解&#xff1a; var (thousands []string{"", "M", "MM", "MMM"}hundreds []string{"", "C", "CC", "CCC", "CD", "D", "DC", "…

ARM v8 Cortex R52内核 02 程序模型 Programmers Model

ARM v8 Cortex R52内核 02 程序模型 Programmers Model 2.1 关于程序模型 Cortex-R52处理器实现了Armv8-R架构。这包括&#xff1a; 所有的异常级别&#xff0c;EL0-EL2。 每个异常级别下的AArch32执行状态。 T32和A32指令集&#xff0c;其中包括&#xff1a; 浮点运算。 …

数据结构--树和二叉树

树和二叉树 1.树概念及结构树的概念树的相关概念树的表示 2.二叉树概念及结构概念特殊的二叉树二叉树的性质 3.二叉树顺序结构及实现4.二叉树链式结构及实现二叉树的顺序结构二叉树的前&#xff0c;中&#xff0c;后序遍历层序遍历 1.树概念及结构 树的概念 树是一种非线性的…

我做的小程序,一下流量就爆了【小游戏:你对颜色敏感吗】

大家好&#xff0c;我是鬼哥&#xff0c;一位8年前端从业者&#xff0c;也是一位全栈开发&独立开发者&#xff0c; 最近有点浮躁&#xff0c;可笑的是2024年已经过去一个季度了&#xff0c;我今年的目标貌似都还没正式开始。 本来去年下半年计划今年开始&#xff0c;正式运…

Java集合——Map、Set和List总结

文章目录 一、Collection二、Map、Set、List的不同三、List1、ArrayList2、LinkedList 四、Map1、HashMap2、LinkedHashMap3、TreeMap 五、Set 一、Collection Collection 的常用方法 public boolean add(E e)&#xff1a;把给定的对象添加到当前集合中 。public void clear(…

线程池详解并使用Go语言实现 Pool

写在前面 在线程池中存在几个概念&#xff1a;核心线程数、最大线程数、任务队列。 核心线程数指的是线程池的基本大小&#xff1b;也就是指worker的数量最大线程数指的是&#xff0c;同一时刻线程池中线程的数量最大不能超过该值&#xff1b;实际上就是指task任务的数量。任务…

KK全域电商,全体系打造实操课,多平台打造电商逻辑体系

实操课详细指导分析流程 资深运营老师陪伴式答疑 课程下载&#xff1a;https://download.csdn.net/download/m0_66047725/89013409 更多资源下载&#xff1a;关注我。 课程内容&#xff1a; 1先导课(拍下请看).mp4 2为什么要做小..红营 .mp4 3小红营适合什么类目的产品,…

linux之文件系统、inode和动静态库制作和发布

一、背景 1.没有被打开的文件都在磁盘上 --- 磁盘级文件 2.对磁盘级别的文件&#xff0c;我们的侧重点 单个文件角度 -- 这个文件在哪里&#xff0c;有多大&#xff0c;其他属性是什么&#xff1f; 站在系统角度 -- 一共有多少文件&#xff1f;各自属性在哪里&#xff1f…

UI自动化框架搭建以及面试题详解(上)

UI自动化框架搭建以及面试题 UI自动化面试题框架面试题那你讲下如何搭建现成的框架公司里面的框架是你搭建的么请结合你的项目讲解一下你的框架是如何搭建的 PO模式什么是 PO 模式PO 模式的封装原则有哪些 DDT驱动模式什么的项目适合ddt ddt四种模式ddt处理各种类型数据 自动化…

软考--软件设计师(软件工程总结3)

目录 1.面向对象技术 2。面向对象分析 3.面向对象程序设计&#xff08;选用一种面向对象的程序语言&#xff09; 4.面向对象测试 5.UML ​编辑6.UML的图 ​编辑7.设计模式 1.面向对象技术 面向对象对象继承类消息通信 对象&#xff1a;是基本运行时的实体&#xff0c;包…

使用Android完成案例教学

目录 题目&#xff1a;完成在Android平台下2个玩家分别利用2个手机连接在同一局域网下通过滑动摇杆分别使红飞机和黄飞机移动的开发。&#xff08;全代码解析&#xff09; 题目&#xff1a;完成在Android平台下2个玩家分别利用2个手机连接在同一局域网下通过滑动摇杆分别使红飞…

Open CASCADE学习|旋转变换

物体在三维空间中的旋转变换操作通常可以通过三种不同的方式来表示&#xff1a;矩阵&#xff08;Matrix&#xff09;、欧拉角&#xff08;Euler Angles&#xff09;和四元数&#xff08;Quaternion&#xff09;。下面详细解释这三种表示方法。 矩阵&#xff08;Matrix&#xf…

【51单片机入门记录】RTC(实时时钟)-DS1302应用

目录 一、DS1302相关写函数 &#xff08;1&#xff09;Write&#xff3f;Ds1302 &#xff08;2&#xff09;Write&#xff3f;Ds1302&#xff3f;Byte 二、DS130相关数据操作流程及相关代码 &#xff08;1&#xff09;DS1302初始化数据操作流程及相关代码 (shijian[i]/10&…

【学习分享】小白写算法之插入排序篇

【学习分享】小白写算法之插入排序篇 前言一、什么是插入排序算法二、插入排序算法如何实现三、C语言实现算法四、复杂度计算五、算法稳定性六、小结 前言 要学好每个算法&#xff0c;我觉得需要先总结出规律&#xff0c;然后自己去推演一遍&#xff0c;加深记忆&#xff0c;否…

阿里云8核32G云服务器租用优惠价格表,包括腾讯云和京东云

8核32G云服务器租用优惠价格表&#xff0c;云服务器吧yunfuwuqiba.com整理阿里云8核32G服务器、腾讯云8核32G和京东云8C32G云主机配置报价&#xff0c;腾讯云和京东云是轻量应用服务器&#xff0c;阿里云是云服务器ECS&#xff1a; 阿里云8核32G服务器 阿里云8核32G服务器价格…

【记录】LangChain|llama 2速通版

官方教程非常长&#xff0c;我看了很认可&#xff0c;但是看完了之后呢就需要一些整理得当的笔记让我自己能更快地找到需求。所以有了这篇文章。【写给自己看的&#xff0c;里面半句废话的解释都没有&#xff0c;如果看不懂的话直接看官方教程再看我的】 我是不打算一开始就用…

Jenkins (四) - 搭建 Docker SonarQube

Jenkins (四) - 搭建 Docker SonarQube 拉取 SonarQube $ docker pull sonarqube拉取 postgres $ $ docker pull postgres运行 postgres $ docker run -itd \ -e TZAsia/Shanghai -e POSTGRES_USERtester \ -e POSTGRES_PASSWORD123456 \ -p 5432:5432 \ -v /home/tester/d…