Java O(n) clean solution with explanation


  • 0
    X
    public class Solution {
        public void nextPermutation(int[] nums) {
            for(int i=nums.length-2;i>=0;i--){
                // find the first number smaller than its next
                if(nums[i]<nums[i+1]){
                    // find the smallest number larger than nums[i] in the array after i
                    int j=i+2;
                    for(;j<nums.length;j++){
                        if(nums[j]<=nums[i]) break;
                    }
                    // swap i and j-1
                    nums[i]^=nums[j-1];
                    nums[j-1]^=nums[i];
                    nums[i]^=nums[j-1];
                    
                    // sort i+1 - end
                    Arrays.sort(nums, i+1, nums.length);
                    return;
                }
            }
            Arrays.sort(nums);
        }
    }
    

    The idea is to iterate from end and find the first number smaller than its next. Then swap it with the next bigger number in the latter array. At last sort the latter array in ascending order. The algorithm iterates the array once, and the time complexity is O(n).


Log in to reply
 

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