数组的下一个排列

数组的下一个排列

问题

这个题目说的是，给你一个整数数组，每一个元素是一个 0 到 9 的整数，数组的排列形成了一个有效的数字。你要找到数组的下一个排列，使它形成的数字是大于当前排列的第一个数字。如果当前排列表示的已经是最大数字，则返回这个数组的最小排列。

比如说，给你的数组是：

2, 1, 8, 4, 2, 1

这个排列表示整数 218421，你要返回的下一个排列是：

2, 2, 1, 1, 4, 8

表示 221148，这是数组中的元素所能组成的数字中，大于当前排列的第一个数字。

再比如说，给你的数组为：

4, 2, 1

你没有办法给出一个比它更大的排列，于是返回这些数字所能构成的最小排列：

1, 2, 4

代码

public class AlgoCasts {

  private void swap(int[] nums, int i, int j) {
    int tmp = nums[i];
    nums[i] = nums[j];
    nums[j] = tmp;
  }

  // Time: O(n), Space: O(1)
  public void nextPermutation(int[] nums) {
    if (nums == null || nums.length < 2) return;
    int n = nums.length;
    int p = n - 2;
    while (p >= 0 && nums[p] >= nums[p+1]) --p;

    if (p >= 0) {
      int i = n - 1;
      while (i > p && nums[i] <= nums[p]) --i;
      swap(nums, i, p);
    }
    for (int i = p+1, j = n-1; i < j; ++i, --j)
      swap(nums, i, j);
  }

}