Paincker

LeetCode：下一个排列

发表于 分类于 阅读次数： Valine： 本文字数： 1.9k 阅读时长 ≈ 2 分钟

题目

31. 下一个排列

计算字典序排列的下一个排列，原地算法。

例如 1,2,3 的字典序排列如下。

1
2
3
4
5
6
1  2  3
1  3  2
2  1  3
2  3  1
3  1  2
3  2  1

分析

对于 123 做分析发现：

  • 当所有值递减（或相等）时，也就组成了最大值，下一个排列为全部翻转得到的最小值。
  • 当最后两位递增时，下一个排列只需要交换最后两位即可，例如 1 2 3 --> 1 3 2。
  • 当最后两位递减（或相等）时，不能交换最后两位，而需要让倒数第三位增大，也就是从后面找一个刚好更大一点的数据填上去，为了原地操作，直接交换位置。例如 1 3 2 --> 2 3 1 。

上面第三种情况比较复杂，再找个复杂的例子：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
5  2  4  3  1
      ———————
      找到末尾最长的递减序列，[4 3 1] 已经是最大的了，想增加数值，只能增加高位

5  2  4  3  1
      ———————
         ↑
        找到了刚好比2大的数字3

5  2  4  3  1
      ———————
   ↑     ↑
   2 改为 3，原地操作，直接交换

5  3  4  2  1
      ———————
      ↑  ↑  ↑
      需要将 [4 2 1] 改为最小值，即 [1 2 4]
      发现 [4 2 1] 刚好是倒序，翻转即可

5  3  1  2  4
      ———————

考虑到数组中可能有重复元素，再找一个例子：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
8  2  4  3  3‘ 2’ 2“ 1
   ↑  ————————————————

8  2  4  3  3‘ 2’ 2“ 1
   ↑  ———↑————————————
   如果2和任意一个3交换，

8  3  4  2  3‘ 2‘ 2“ 1
      ————————————————
      后面的数据就乱了，只能重新排序成最小值。

8  2  4  3  3‘ 2’ 2“ 1
   ↑  ——————↑—————————
   如果2和最末尾的3交换，

8  3‘ 4  3  2  2‘ 2“ 1
      ————————————————
      后面的数据刚好还是递减的，直接翻转就能得到最小值。

8  3‘ 1  2“ 2’ 2  3  4
      ————————————————

所以完整的逻辑是：

  1. 如果整个数组都是递减的，说明是最大值，下一个排列应该是最小值，全部翻转即可。
  2. 找到末尾最长的递减序列，其起始index记为k，满足：
    • [k-1] < [k] >= [k+1] >= .. >= [n-1]。
  3. 从最末尾开始，找到第一个刚好大于 [k-1] 的数字 [x]，因为 [k] > [k-1] ，这个数字肯定是存在的。
  4. 交换 [k-1] 和 [x]，然后翻转 [k] ~ [n-1]。

代码：

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
35
36
37
38
39
40
41
42
43
44
45
46
47
48
class Solution {
    public void nextPermutation(int[] nums) {
        if (nums == null  nums.length <= 1) return;
        int k = findLastDecSeq(nums);
        if (k == 0) {
            reverse(nums, 0, nums.length-1);
            return;
        }
        int x = findLastLagerVal(nums, k, nums[k-1]);
        swap(nums, x, k-1);
        reverse(nums, decIndex, nums.length-1);
    }

    // return k, [k-1] < [k] >= [k+1] >= ... >= [n-1]
    // find longest decreasing sequence in the end
    public int findLastDecSeq(int[] a) {
        for (int i = a.length - 1; i > 0; --i) {
            if (a[i] > a[i-1]) {
                return i;
            }
        }
        return 0;
    }

    // return largest x, [x] > target
    public int findLastLagerVal(int[] a, int start, int target) {
        for (int i = a.length-1; i >= start; --i) {
            if (a[i] > target) return i;
        }
        return start;
    }

    public void swap(int[] a, int x, int y) {
        int t = a[x];
        a[x] = a[y];
        a[y] = t;
    }

    public void reverse(int[] a, int start, int end) {
        while (start < end) {
            int t = a[start];
            a[start] = a[end];
            a[end] = t;
            start++;
            end--;
        }
    }
}
相关文章