leetcode-program

Question 31: Next Permutation

Link

Solution

Step 1: search from the right to find the first i that satisfies nums[i-1] < nums[i]. Let i = 0 if not found.

Note that nums[i:] is in descending order.

Step 2 (apply only if i != 0): search nums[i:] from the left to find nums[j] that just larger than nums[i-1]. Choose the larger j if there are duplicates (to maintain the descending order). Swap nums[i-1] and nums[j].

Note that nums[i:] is still in descending order after swaping.

Step 3: reverse nums[i:].

Code

Java

public class Solution {
    public void nextPermutation(int[] nums) {
        for (int i = nums.length - 1; i >= 0; --i) {
            if (i != 0 && nums[i - 1] >= nums[i]) continue;

            if (i != 0) {
                int next = Integer.MAX_VALUE;
                int pos = -1;

                for (int j = i; j < nums.length; ++j) {
                    if (nums[j] > nums[i - 1] && nums[j] <= next) {
                        next = nums[j];
                        pos = j;
                    }
                }

                if (pos != -1) {
                    nums[pos] = nums[i - 1];
                    nums[i - 1] = next;
                }
            }

            for (int l = i, r = nums.length - 1; l < r; ++l, --r) {
                int t = nums[l];
                nums[l] = nums[r];
                nums[r] = t;
            }

            break;
        }
    }
}

This site is open source. Improve this page.