My java Solution(20ms)


  • 0
    Y
    public class Solution {
        public void nextPermutation(int[] nums) {
            if(nums.length<2)
                return;
            int pos = -1;
            for(int i=0;i<nums.length-1;i++){
                if(nums[nums.length-1-i]>nums[nums.length-i-2]){
                    pos = nums.length-i-2;
                    break;
                }
            }
            if(pos==-1){
            	Arrays.sort(nums,0,nums.length);
                return;
            }
            for(int i=nums.length-1;i>=0;i--){
                if(nums[i]>nums[pos]){
                    int temp = nums[i];
                    nums[i] = nums[pos];
                    nums[pos] = temp;
                    Arrays.sort(nums,pos+1,nums.length);
                    return;
                }
            }
        }
    }
    

    From the tail of array, it will find the first item, the next-item of which is greater. For example, "1,2,3,4", it will find the item "3". One more example, "1,2,3,4,1,1", the result it find is the item "3".
    If it find the item, find the most close item to the item found. Swap them and sort the array from the positon to the last. If it can't find the item above, reverse the array(I use Arayy.sort function:). it's better if you write the reverse function).


Log in to reply
 

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