[LeetCode] Next Permutation

[LeetCode] Next Permutation

Next Permutation Total Accepted: 14635 Total Submissions: 57694 My Submissions
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,3 → 1,3,2
3,2,1 → 1,2,3

1,1,5 → 1,5,1

分三步，

1. 從後往前，找到第一個不是遞增的數

2. 在從後往前找到一個比剛才那個數大的第一個數，交換位置

3. 在將第一個數後面的序列反轉

public class Solution {
    public void nextPermutation(int[] num) {
        if (num == null || num.length < 2) {
            return;
        }
        
        int len = num.length;
        
        int i = len - 2;
        for (; i >= 0; i--) {
            if (num[i] < num[i + 1]) {
                break;
            }
        }
        
        if (i == -1) {
            reverse(num, 0, len - 1);
            return;
        }
        
        for (int j = len - 1; j > i; j--) {
            if (num[j] > num[i]) {
                swap(num, j, i);
                break;
            }
        }
        
        reverse(num, i + 1, len - 1);
        return;
    }
    
    private void reverse(int[] num, int start, int end) {
        while (start < end) {
            swap(num, start, end);
            start++;
            end--;
        }
    }
    
    private void swap(int[] num, int i, int j) {
        int temp = num[i];
        num[i]  = num[j];
        num[j] = temp;
    }
}