Poison

31. Next Permutation

发表于 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
class Solution {
    public void nextPermutation(int[] nums) {
        int smallerIndex = -1;
        for (int i = nums.length - 1; i > 0; i--) {
            if (nums[i - 1] < nums[i]) {
                smallerIndex = i - 1;
                break;
            }
        }

        if (smallerIndex != -1) {
            for (int i = nums.length - 1; i > smallerIndex; i--) {
                if (nums[i] > nums[smallerIndex]) {
                    swap(nums, i, smallerIndex);
                    break;
                }
            }
        }

        reverse(nums, smallerIndex + 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) {
        while (i < j) {
            swap(nums, i++, j--);
        }
    }
}

由于题目要求需按照下一个更大的排列，那么容易想到通过交换数组中的元素实现，容易想到的是从右侧像左侧搜索，如果能把更低位的较大值与较高位的较小值交换，那么就能构成更大的序列，如数组：[4, 9, 5, 3]，容易想到的是将 4 与 9 交换得到：[9, 4, 5, 3]，但是通过观察原数组易知，交换至左侧元素的值应大于左侧元素且应尽量接近左侧元素值，所以此时应该将 4 与 5 交换，以使得到的排列尽可能地接近原排列，交换后的数组为：[5, 9, 4, 3]，此时左侧元素值已经变大，那么此时还应该让剩下的元素组成的数值尽可能地小，此时只需将剩下的元素倒序即可（倒序前右侧元素非严格单调递减）。

Reference

31. Next Permutation