Super short and consice Java O(n) code


  • 0
    S

    The algorithm is basically the same with other top vote answers:

    Find the maximum i, so that nums[i]<nums[i+1] and nums[i+1] ... nums[len-1] is in descending order. Then, reverse and swap as the following example shows:

    Example:
    142321:
    21, descending order, continue.
    321, descending order, continue.
    2321, no longer descending order. Reverse the tailing 321 to 123, we get 142-123. Inside 123, 3 is the first one which is greater then 2 (the digit before 123), so 3 should replace digit 2. We get 143-122.

    public void nextPermutation(int[] nums) {
    	if (nums == null) {return;}
    		
    	int i = nums.length - 2;
    	while (i >= 0 && nums[i] >= nums[i + 1]){ i--;}
    	
    	for (int j = i + 1; j <= (i + nums.length) / 2; j++) {
    		int temp = nums[j]; nums[j] = nums[nums.length + i - j]; nums[nums.length + i - j] = temp;
    	}
    		
    	if (i >= 0) {
    		int j = i + 1;
    		while (nums[i] >= nums[j]) {j++;}
    		int temp = nums[i]; nums[i] = nums[j]; nums[j] = temp;
    	}
    }
    

Log in to reply
 

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