https://leetcode.cn/problems/next-permutation/description/
字节面试题,非常经典的逻辑思维题
1、找到第一个下降点,说明这个点可以变得稍微大一点以至于让整个排列变得更加大
为什么,仔细想想,后面都是倒序了怎么都不可能变得更加大了
2、下降点变成多大呢?变成后面比它大的最小的数就可以了
3、这一位已经比原来的大了,后面不管怎么样,这个排列都会比原来的大,要是这个排列尽可能地小,只需要对后面的排个序文章来源:https://www.toymoban.com/news/detail-757426.html
可以看一下这张图更加容易理解:
代码:
文章来源地址https://www.toymoban.com/news/detail-757426.html
class Solution {
public void nextPermutation(int[] nums) {
//从右至左找第一个下降点,如果找不到,说明是倒序排序翻转一下就可以了
int down = -1;
int cur = nums.length-1;
while(cur>=1){
if(nums[cur]>nums[cur-1]){
down = cur-1;
break;
}
cur--;
}
//找不到
if(down==-1){
for(int i=0;i<nums.length/2;i++){
int temp = nums[i];
nums[i] = nums[nums.length-i-1];
nums[nums.length-i-1] = temp;
}
return ;
}
//找翻转哪一个点
while(cur<nums.length){
if(nums[cur]<=nums[down])
break;
cur++;
}
//找到的是第一个小于等于down的,还要再-1;
cur--;
//这个数移到down
int temp = nums[cur];
nums[cur] = nums[down];
nums[down] = temp;
//再排个序
//可以使用翻转,因为后面必定倒序
//1、Arrays.sort(nums,down+1,nums.length);
//局部反转写起来容易错,还是推荐直接排序
for(int i=1;i<=(nums.length-(down+1)+1)/2;i++){
int t = nums[down+i];
nums[down+i] = nums[nums.length-i];
nums[nums.length-i] = t;
}
}
}
到了这里,关于力扣思维题/经典面试题——下一个排序的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!