LeetCode HOT 100:下一个排列
题目:31. 下一个排列
题目描述:
本题是给你一个整数数组,返回该数组的下一个线性顺序排列。
举个例子:给你一个[1, 2, 3]
的数组,他的线性排列顺序从小到大依次为[1, 3, 2],[2, 1, 3],[2, 3, 1],[3, 1, 2],[3, 2, 1]
所以如果给你数组是[1, 2, 3]
,就应该返回[1, 3, 2]
,如果数组是[1, 3, 2]
,就应该返回[2, 1, 3]
题目要求,如果已经是最大线性顺序排列,应当返回最小线性顺序排列,例如数组[3, 2, 1]
,应返回[1, 2, 3]
,可以将其理解为一个环。
步骤:
这道题需要从右往左遍历。
1、从右往左遍历,从n - 2
下标开始遍历,每一个遍历元素下标为i
,如果i
一直都大于等于i+1
,那么说明该数组已经是最大线性顺序排列,直接反转数组,返回最小线性顺序排列即可。
例如:[5, 4, 3, 3, 1, 1]
,直接反转数组,返回[1, 1, 3, 3, 4, 5]
即可
2、如果在从右往左遍历过程中,一直在升序,突然有一个元素降序了,将该元素下标记录下来,记为较小数,下标为 less
3、然后找到less
右边中,大于less
的数中最小的那个数的下标,记为more
下标。将这两个下标进行交换
4、将原来less
下标之后的元素反转一遍,即可得到原数组的下一个线性顺序排列。
解释:
举一个例子,解释上面的操作为什么能得到原数组的下一个线性顺序排列。
原数组[1, 2, 4, 7, 6, 3, 2, 1]
,less
下标元素就是4,因为4是首次降序的元素,所以4后面的元素一定是最大线性顺序[7, 6, 3, 2, 1]
,
且因为4是首次降序的元素,则后面有比4大的元素,所以4前面的元素肯定不需要动。
所以暂时抛弃4前面的元素,求以4开头一直到结束的数组[4, 7, 6, 3, 2, 1]
,下一线性顺序即可。
很容易理解,以4开头的[4, 7, 6, 3, 2, 1]
数组的下一线性顺序数组一定是以6开头,即下标为more
的元素,因为6是4后面大于4的数字中最小的那个,所以6一定是下一线性顺序数组的开头,将4和6交换之后,数组变为[6, 7, 4, 3, 2, 1]
。
然后,[4, 7, 6, 3, 2, 1]
数组中,是以4开头的最大线性顺序,他的下一线性顺序,肯定是以6开头的最小线性顺序,所以将6后面的元素反转即可,将[6, 7, 4, 3, 2, 1]
变为[6, 1, 2, 3, 4, 7]
。
最终,原数组[1, 2, 4, 7, 6, 3, 2, 1]
,下一个线性顺序排列为[1, 2, 6, 1, 2, 3, 4, 7]
。
代码:
public void nextPermutation(int[] nums) {
if (nums == null || nums.length < 2) return;
int N = nums.length;
// 从右往左第一次降序的位置
int firstLess = -1;
for (int i = N - 2; i >= 0; i--) {
if (nums[i] < nums[i + 1]) {
firstLess = i;
break;
}
}
if (firstLess == -1) {
reverse(nums, 0, N - 1);
} else {
// 找到最靠右的,同时比nums[firstLess]大的数的下标
int rightClosestMore = -1;
// 这里也可以使用二分进行优化
for (int i = N - 1; i > firstLess; i--) {
if (nums[i] > nums[firstLess]) {
rightClosestMore = i;
break;
}
}
swap(nums, firstLess, rightClosestMore);
reverse(nums, firstLess + 1, N - 1);
}
}
public void reverse(int[] nums, int start, int end) {
while (start < end) {
swap(nums, start, end);
start++;
end--;
}
}
public void swap(int[] nums, int i, int j) {
int temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
}
最新文章
- .net之工作流工程展示及代码分享(二)工作流引擎
- fcc的中级算法题
- Unit Tests
- c++ builder TreeView控件节点遍历
- [MySql] 设置了UTF8,中文存数据库中仍然出现问号
- Android实例-全屏显示程序(XE10+小米2)(无图)
- refreshcontrol 实现下拉刷新的功能
- 【Android Studio】没有先安装JDK
- Jackson序列化实例
- python入门编程之基础
- 源码实现 -->; strcpy
- [USACO13OPEN]照片Photo
- 【转】搭建Java版WebService
- Kattis之旅——Eight Queens
- Table展开行
- centos7 Apache 2.4.6 多域名多网站配置
- [转]如何使用Fiddler抓取指定浏览器的数据包
- 通过实现一个TableView来理解iOS UI编程
- webStorm配置es6转es5
- 苹果推送服务器端证书配置.pem生成