O(n) java solution


  • 0
    L
    public void nextPermutation(int[] nums) {
        if(nums.length==0||nums.length==1) return;
        int end=nums.length-1;
        while(nums[end]<=nums[end-1]){
            end--;
            if(end==0)  break;
        } 
        int index=end-1;
        int temp=0;
        if(end>0){//if not descend order find Min(nums[end],nums[end+1]...nums[nums.length-1])>nums[index]
          while(nums[end]>nums[index]){
            end++;
            if(end==nums.length) break;
          } 
          temp=nums[index];//exchage nums[index] and data has found
          nums[index]=nums[end-1];
          nums[end-1]=temp;
        }
        for(int i=index+1;i<(nums.length+index+1)/2;i++){//sorted nums[index+1],nums[index+2]...in ascending 
            temp=nums[i];
            nums[i]=nums[nums.length+index-i];
            nums[nums.length+index-i]=temp;
        }
        return ;
    }

Log in to reply
 

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