LeetCode 31 - Next Permutation

作者 QIFAN 日期 2017-01-14
LeetCode 31 - Next Permutation

原题链接: 31. Next Permutation


题干

给定一个数字数组,返回它按照 Lexicographical 升序排序的下一个 permutation 。如果不存在这样的 permutation ,就返回一个按数字升序的。数组内的替换要求 in-place 。

举例
输入: [100, 2, 31]
返回: [100, 31, 2]
解释: [100, 2, 31] 的所有 permutation 按照 lexicographical 排序是 [100, 2, 31] , [100, 31, 2] , [2, 100, 31] , [2, 31, 100] , [31, 100, 2] , [31, 2, 100] 。[100, 2, 31] 的下一个是 [100, 31, 2] 。

思路

先做出一个假设:存在重复元素

要求相邻的 permutation ,所以应该保持前缀尽可能多位的相同。对于首次出现的不同通的两个元素。我想到四种情况:

  • 前缀 + 递增
  • 前缀 + 递增 + 递减
  • 递增 + 递减
  • 递增
  • 递减

先不管 lexicographical ,先考虑单纯的数字排序来理清思路。上述四种可以概括为一个情况:前缀 + 递增 + 递减。递减为非严格,递增为严格,前缀、递增、递减可为空,递增部分只包含两个元素。

假设的递增部分的第一个元素为 a ,第二个元素为 b ,递减部分的最小元素为 c 。abc 里 a 和 c 的大小关系不确定。

  • a >= c ,即 b > a >= c 。因为 a 后面是一串递增,是以 a 开头的 permutation 的最大值,所以下一个 permutation 为大于 a 的最小元素开头,即 c ~ b 之间大于 a 的最小值 x ,而一串元素 permutation 的最小为递增,因此最终形式为 x + 递增
  • a < c ,即 b > c > a 。同上理由,最终形式为 c + 递增

还有一种情况就是 a 不存在,即整个数组为递减,这是 permutation 的最大值,那就是返回递增 permutation 了。

排序之所以用 QuickSort 是因为:

  • in-place
  • 数组已经是大部分有序

worst case 为整串递减,此时时间复杂度为 $O(nlogn) $ 。

代码:

public void nextPermutation(int[] nums) {
if (nums.length <= 1) {
return;
}
int b = nums.length - 1;
int a = b - 1;
// 寻找递增部分
while (a > 0 && nums[a] >= nums[b]) {
b = a--;
}
// 整串递减
if (nums[a] >= nums[b]) {
quickSort(nums, 0, nums.length - 1);
} else {
// 递减部分最小值
int c = nums.length - 1;
if (nums[a] >= nums[c]) {
// 寻找比 a 大的最小值
int x = nums.length;
while (x > a && nums[--x] <= nums[a]);
swap(nums, a, x);
} else {
swap(nums, a, c);
}
quickSort(nums, a + 1, nums.length - 1);
}
}
private void swap(int[] nums, int a, int b) {
int temp = nums[a];
nums[a] = nums[b];
nums[b] = temp;
}
private int partition(int[] nums, int lo, int hi, int pIndex) {
int pivot = nums[pIndex];
while (lo < hi) {
while (lo < hi && nums[lo] < pivot) {
lo++;
}
while (lo < hi && nums[hi] > pivot) {
hi--;
}
if (lo == hi) {
swap(nums, pIndex, lo);
return lo;
}
swap(nums, lo++, hi--);
}
return pIndex;
}
private void quickSort(int[] nums, int lo, int hi) {
if (lo >= hi) {
return;
}
int pIndex = lo + (hi - lo) / 2;
pIndex = partition(nums, lo, hi, pIndex);
quickSort(nums, lo, pIndex - 1);
quickSort(nums, pIndex + 1, hi);
}