leetcode 31. 下一个排列

难度:中等
频次:

题目:

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

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

必须 原地 修改,只允许使用额外常数空间。
leetcode 31. 下一个排列

解题思路:找规律

leetcode 31. 下一个排列

注意:

  • 如图,先从后到前找到异类点 不是上升函数的点
    - 这个时候可能没有异类点,那就直接将全部序列反转一下就行。
    - 如果有异类点,执行下面的操作
  • 之前的序列叫做目标序列,从目标序列中找到刚好比异类点大的点—>目标点【也是从后到前】
  • 异类点目标点交换
  • 最后将交换后的目标序列反转一下即可

代码

class Solution {
    public void nextPermutation(int[] nums) {
        int len=nums.length;
        int n=len-2; 
        //注意这里有等于号
        //这里要铆钉n的位置
        //1.从后到前,先找到转折点(不是递增)【异类】
        while(n>=0&&nums[n]>=nums[n+1]){
            n--;
        }
        //如果刚好n遍历到-1结束,即所有的数字都没有转折点,那就不用交换位置,直接逆序就行
        //如果能找到转折点(异类)
        if(n>=0){
            //先交换比这个异类和从后到前第一个大于异类的值
            for(int j=len-1;j>n;j--){
                    if(nums[n]<nums[j]){
                        swap(nums,n,j);
                        //这个break跳出不能没有,否则会交换很多个数字
                        break;
                    }
                }
        }
        //从n+1的下标到len-1的位置逆序
        reversal(nums,n+1);
    }
    //这不用说了
    public void swap(int[] nums,int a,int b){
        int temp=nums[a];
        nums[a]=nums[b];
        nums[b]=temp;
    }
    //简单的交换不能错
    public void reversal(int[] nums,int a){
        int len=nums.length;
        for(int i=a;i<=(len-1+a)/2;i++){
            swap(nums,i,len-1+a-i);
        }
    }
}
上一篇:Daily Leetcode-2链表


下一篇:Hillstone Secure Connect下载