目录
- 350-两个数组的交集
- 283-移动零
- 1-两数之和
- 25-K 个一组翻转链表
- 581-最短无序连续子数组
- 合并区间
- 螺旋矩阵
- 数组中相加和为0的三元组
- 数组中出现次数超过一半的数字
- 字符串出现次数的TopK问题
- 206-反转链表
- 160-相交链表
- 19-删除链表的倒数第N个节点
- 21-合并两个有序链表
- 31-下一个排列
- 链表K位翻转
- 链表排序-归并算法
- 判断链表中是否有环
- 设计LRU缓存结构
- 两个链表的第一个公共结点
- 两个链表生成相加链表
- 合并N个有序链表
- 链表内指定区间反转
31-下一个排列
访问量:1845
一、题目简介
实现获取下一个排列的函数,算法需要将给定数字序列重新排列成字典序中下一个更大的排列。
如果不存在下一个更大的排列,则将数字重新排列成最小的排列(即升序排列)。
必须原地修改,只允许使用额外常数空间。
以下是一些例子,输入位于左侧列,其相应输出位于右侧列。
1,2,3 → 1,3,2
3,2,1 → 1,2,3
1,1,5 → 1,5,1
地址:https://leetcode-cn.com/problems/next-permutation/
二、解法
1、解法1
func nextPermutation(nums []int) { numsLen := len(nums) if numsLen <= 1{ return } var ( frontIndex = numsLen -2 backIndex = numsLen -1 ) for frontIndex >= 0{ if nums[frontIndex] < nums[backIndex] { break } frontIndex --/* */ backIndex -- } if frontIndex >= 0 { // 从front后面找一个比frontIndex大,且最下的元素插入frontIndex,剩下的元素倒排 backIndex = numsLen -1 for nums[frontIndex] >= nums[backIndex] { backIndex -- } tmp := nums[frontIndex] nums[frontIndex] = nums[backIndex] nums[backIndex] = tmp frontIndex ++ } else { frontIndex = 0 } // 需要排序,从小到大 backIndex = numsLen -1 // 首尾交换 for frontIndex < backIndex { tmp := nums[frontIndex] nums[frontIndex] = nums[backIndex] nums[backIndex] = tmp frontIndex ++ backIndex -- } }
本文为原创文章,请尊重辛勤劳动,如需转载,请保留本文地址
若您感觉本站文章不错,读后有收获,不妨赞助一下?
我要赞助