Share O(n) simple Java solution


  • 1
    T

    The idea is very simple,we simply iterate through the nums to see where ascending order ends,and then we are simply replacing that number(where ascending ends) replace with the least one bigger and reverse from that point.

    public class Solution {
        public void nextPermutation(int[] nums) {
            if(nums.length ==1){
                return;
            }
            int len = nums.length;
            int i=len-1;
            while(i>0 && nums[i]<=nums[i-1]){
                --i;
            }
            if(i==0)
            reverse(nums,0,len-1);
            else
            {
                int c=nums[i-1];
                int k=len-1;
                while(k>i-1 && nums[k]<=c){
                    --k;
                }
                nums[i-1]=nums[k];
                nums[k]=c;
                reverse(nums,i,len-1);
            }
            
        }
        private void reverse(int[] nums,int start,int end){
            int n=(-start+end+1)/2;
            for(int i=0;i<n;++i){
                int c = nums[start+i];
                nums[start+i]=nums[end-i];
                nums[end-i]=c;
            }
        }
        
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.