O(n) optimized simple code in Java


  • 0
    S
    1. check if nums[i] > nums[i-1] exists;
    2. if yes,
      2.1 find the one that is just greater than nums[i-1];
      2.2 swap & reverse;
    3. else,
      3.1 reverse the array;
    public class Solution {
        public void nextPermutation(int[] nums) {
            if (nums == null || nums.length < 2) return;
            int next = 0;
            for (int i = nums.length-1; i > 0; i--) {
                if (nums[i] > nums[i-1]) {
                    next = i-1;
                    while (next+1 < nums.length && nums[next+1] > nums[i-1])
                        next++;
                    swap(nums, next, i-1);
                    for (int delta = 0; i+delta < nums.length-1-delta && nums[i+delta] > nums[nums.length-1-delta]; delta++)
                        swap(nums, i+delta, nums.length-1-delta);
                    return;
                }
            }
            for (int delta = 0; delta < nums.length-1-delta; delta++)
                swap(nums, delta, nums.length-1-delta);
        }
        
        private void swap(int[] nums, int i, int j) {
            int swap = nums[i];
            nums[i] = nums[j];
            nums[j] = swap;
        }
    }
    

Log in to reply
 

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