力扣 下一个排列

server/2025/2/26 10:34:50/

交换位置,双指针,排序。

题目

下一个排列即在组成的排列中的下一个大的数,然后当这个排列为降序时即这个排列最大,因为大的数在前面,降序排列的下一个数即升序。所以,要是想找到当前排列的下一个排列,肯定是先从后面开始找,因为后面的数做交换才使得排列尽可能接近。可以想一下,从最后一个数往回找时,如果一直是升序,就说明已经是最大了,直到找到那个不是升序的数做交换,即要操作的下一排列了,交换时的数应该是扫描数组的大于目标数的最小数,这样才符合原数组的下一个排列。注意从后往前找的升序即从前往后的降序,找到目标数后,还要处理目标数的后面序列,从前往后看,显然刚刚扫描的序列是降序的,这样后面几个数组成的排列是最大的显然不符合下一个序列。在当前数do过后,后面的数应该是最小的即从前往后升序的状态。

时间复杂度: O(n),空间复杂度: O(1)。

java">class Solution {public void nextPermutation(int[] nums) {int i = nums.length - 2;while (i >= 0 && nums[i] >= nums[i + 1]) {i--;}if (i >= 0) {int j = nums.length - 1;while (j >= 0 && nums[i] >= nums[j]) {j--;}swap(nums, i, j);}reverse(nums, i + 1);}public void swap(int[] nums, int i, int j) {int temp = nums[i];nums[i] = nums[j];nums[j] = temp;}public void reverse(int[] nums, int start) {int left = start, right = nums.length - 1;while (left < right) {swap(nums, left, right);left++;right--;}}
}

也可以用sort方法直接排。

java">class Solution {public void nextPermutation(int[] nums) {int len = nums.length;for (int i = len - 1; i >= 0; i--) {if (i == 0) {Arrays.sort(nums);return;} else {if (nums[i] > nums[i - 1]) {Arrays.sort(nums, i, len);for (int j = i; j <len; j++) {if (nums[j] > nums[i - 1]){swap(nums,j,i-1);return;}}}}}}private void swap(int[] nums, int i,int j){int tmp =nums[i];nums[i]=nums[j];nums[j]=tmp;}
}

找准双指针扫描的范围,对准目标数做操控。 

 


http://www.ppmy.cn/server/170718.html

相关文章

算法与数据结构(格雷编码)

题目 思路 首先我们先看一下格雷编码的一些情况&#xff0c;为了一会方便理解&#xff0c;我们看它的二进制情况。 当n1时&#xff0c;输出[0&#xff0c;1] 当n2时&#xff0c;输出[00,01,11,10] 当n3时&#xff0c;输出[000, 001, 011, 010, 110, 111, 101, 100] 我们可…

lua基础语法学习

lua基础语法学习 文章目录 lua基础语法学习1. 基础2. 输入输出3. 分支结构与循环结构4. 函数5. 元表与元方法6. 面向对象 1. 基础 注释 --单行注释--[[ 多行注释 --]]标识符 标识符以一个字母 A 到 Z 或 a 到 z 或下划线 _ 开头后加上 0 个或多个字母&#xff0c;下划线&…

C#中级教程(1)——解锁 C# 编程的调试与错误处理秘籍

一、认识错误&#xff1a;编程路上的 “绊脚石” 在 C# 编程中&#xff0c;错误大致可分为两类&#xff1a;语法错误和语义错误&#xff08;逻辑错误&#xff09;。语法错误就像是写作文时的错别字和病句&#xff0c;编译器一眼就能识别出来&#xff0c;比如变量名拼写错误、符…

【大模型】Ubuntu下 fastgpt 的部署和使用

前言 本次安装的版本为 fastgpt:v4.8.8-fix2。 最新版本fastgpt:v4.8.20-fix2 问答时报错&#xff0c;本着跑通先使用起来&#xff0c;就没有死磕下去&#xff0c;后面bug解了再进行记录。   github连接&#xff1a;https://github.com/labring/FastGPT fastgpt 安装说明&…

Android平台GB28181接入模块(SmartGBD)技术接入说明

一、技术背景 GB/T 28181-2016/2022是中国国家标准&#xff0c;旨在规范网络视频监控设备的接入与互操作性。本模块的设计目标是使不具备国标音视频能力的 Android 终端能够通过平台注册接入到现有的GB/T 28181-2016/2022服务平台。该模块可广泛应用于智能监控、智慧零售、智慧…

使用Python爬虫获取孔夫子旧书网已售商品数据:调用item_search_sold接口

在二手书市场中&#xff0c;孔夫子旧书网是国内知名的平台&#xff0c;拥有丰富的古籍和二手书资源。通过其提供的API接口&#xff0c;开发者可以方便地获取已售商品的信息&#xff0c;这对于市场分析、价格研究和书籍收藏等领域具有重要价值。本文将详细介绍如何使用Python爬虫…

多智能体集群编队实验平台构成

“智群”多智能体集群编队实验平台是一套基于光学动捕定位为基础的无人机和无人车室内多智能体集群编队实验平台&#xff0c;配套丰富的二次开发例程和简洁的集群控制地面站&#xff0c;支持集群控制、路径规划、目标识别、任务决策等教学任务和算法验证。 实验平台基于NOKOV高…

nodejs npm install、npm run dev运行的坎坷之路

1、前面的种种都不说了&#xff0c;好不容易运行起来oap-portal项目&#xff0c;运行idm-ui项目死活运行不起来&#xff0c;各种报错&#xff0c;各种安装&#xff0c;各种卸载nodejs&#xff0c;卸载nvm&#xff0c;重装&#xff0c;都不好使。 2、甚至后来运行npm install会…