31. Next Permutation

初始解法：
直接调用一次next(nums, 0, nums.length);
例如1, 4, 7, 8, 6
从右往左找第一个比6小的数，与6对调（1,6,7,8,4），然后对6以后的数做sort( 1, 6, 4, 7, 8)

这样可能会出现：
input: [4,2,0,2,3,2,0]
output: [4,2,2,0,0,2,3]
expected: [4,2,0,3,0,2,2]

改进：
首先对末尾k位看调用初始解法能否成功，若不成功，则对末尾k+1位调用……

public class Solution {
    // nums[beg, end)
    public boolean next(int[] nums, int beg, int end) {
        boolean flag = false;
        for (int i = end - 1; i >= beg; i--) {
            for (int j = i - 1; j >= beg; j--) {
                if (nums[i] > nums[j]) {
                    int tmp = nums[j];
                    nums[j] = nums[i];
                    nums[i] = tmp;
                    Arrays.sort(nums, j + 1, end);
                    flag = true;
                    break;
                }
            }
            if (flag == true)
                break;
        }
        return flag;
    }

    public void nextPermutation(int[] nums) {
        for (int i = nums.length - 2; i >= 0; i--) {
            boolean flag = next(nums, i, nums.length);
            if (flag == true)
                break;
            else if (i != 0) {
                continue;
            } else {
                Arrays.sort(nums);
                break;
            }
        }
    }
}