Simple code with explantion


  • 3

    step 1: search from right, find the first i that nums[i] < nums[i + 1]

    step 2: search from right, find the frist j that nums[i] < nums[j]

    step 3: swap nums[i] with nums[j]

    step 4: reverse nums from i + 1 to the end

    in step1, if not find i that nums[i] < nums[i + 1], just reverse nums from 0 to the end.

    as 153642,

    i = 2 is the first one that num[i] < nums[i + 1] from right ,

    j = 4 is the first one that nums[i] < nums[j] from right,

    Swap nums[i] with nums[j], it become 154632.

    Then reverse nums from i + 1(here is 3) to the end, it become 154236.

    So 154236 is the next permutation of 153642.

    This method is find by Fischer and Kruse two hundred years ago.

    public static void nextPermutation(int[] nums) {
    	if (nums == null || nums.length <= 1)
    		return;
    	int i = nums.length - 2;
    	while (i >= 0 && nums[i] >= nums[i + 1]) 
    		i--;
    	if (i < 0) {
    		reverse(nums, 0, nums.length - 1);
    	} else {
    		int j = nums.length - 1;
    		while (j > i && nums[i] >= nums[j])
    			j--;
    		swap(nums, i, j);
    		reverse(nums, i + 1, nums.length - 1);
    	}	
    }
    public static void swap(int[] nums, int i, int j) {
    	int temp = nums[i];
    	nums[i] = nums[j];
    	nums[j] = temp;
    }
    public static void reverse(int[] nums, int begin, int end) {
    	while (begin < end) {
    		swap(nums, begin, end);
    		begin++;
    		end--;
    	}
    }

Log in to reply
 

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