LeetCode 31. Next Permutation

Problem:

Implement next permutation, which rearranges numbers into the lexicographically next greater permutation of numbers.

If such arrangement is not possible, it must rearrange it as the lowest possible order (ie, sorted in ascending order).

The replacement must be in-place, do not allocate extra memory.

Here are some examples. Inputs are in the left-hand column and its corresponding outputs are in the right-hand column.
1,2,31,3,2
3,2,11,2,3
1,1,51,5,1

Solution:

public class Solution {
    public void nextPermutation(int[] nums) {
        int i = 0;
        for (; i < nums.length - 1; i++) {
            if (nums[i] < nums[i+1]) break;
        }
        if (i == nums.length - 1) {
            Arrays.sort(nums);
            return;
        }
        for (i = nums.length - 1; i > 0; i--) {
            if (nums[i-1] < nums[i]) break;
        }
        int pivot = i - 1;
        for (i = nums.length - 1; i > 0; i--)
            if (nums[i] > nums[pivot]) break;
        swap(nums, pivot, i);
        reverse(nums, pivot + 1, nums.length - 1);
    }
    
    private void swap(int[] nums, int i, int j) {
        int tmp = nums[i];
        nums[i] = nums[j];
        nums[j] = tmp;
    }
    
    private void reverse(int[] nums, int i, int j) {
        for (int k = i; k <= (i + j)/2; k++) {
            swap(nums, k, j + i - k);
        }
    }
}

4 thoughts on “LeetCode 31. Next Permutation”

  1. 防曬粉 BB粉底霜 亮麗柔滑打底乳液 亮麗柔滑控油打底乳液 有機幹細胞修護CC霜 潤澤防曬底霜 礦物質潤澤慕斯 礦物質奇幻粉餅 礦物質蜜粉 完美礦物粉底 控油定妝蜜粉 高清控油粉餅 控油蜜 保濕滋潤噴霧 有機抗氧爽膚噴霧 有機抗敏保濕

Leave a Reply

Your email address will not be published. Required fields are marked *