字典序

介绍

所谓字典序，就是按照字典的排列顺序进行排列。首先，先按照首字符进行排序，如果首字符相同，则按照第二个字符进行排序，以此类推。比如一系列由abc三个字符组成的字符串的字典序的排列：abc，acb，bac，bca，cab，cba

字典序算法

字典序算法的目的是为了找一个字符串的下一个字典序。例如：有一系列字符串是由abcdefg组成的，他们按照字典顺序排列。求字符串abcdgef的下一个排序，这类问题。

这里可以看下leetcode的一道题目：31. 下一个排列 - 力扣（Leetcode）

过程

主要步骤：

  1. i从字符串末尾向前进行遍历，找到一个字符s[i] < s[i + 1]
  2. j从字符串末尾向前进行遍历，找到一个字符s[j] > s[i]
  3. 交换s[i]和s[j]
  4. 对i位置以后的字符进行倒转（不包括i）

这样的到的结果就是原字符串的下一个排序了。

实现

这里以这道题为例：31. 下一个排列 - 力扣（Leetcode）

整数数组的一个 排列 就是将其所有成员以序列或线性顺序排列。

  • 例如，arr = [1,2,3] ，以下这些都可以视作 arr 的排列：[1,2,3]、[1,3,2]、[3,1,2]、[2,3,1] 。

整数数组的 下一个排列 是指其整数的下一个字典序更大的排列。更正式地，如果数组的所有排列根据其字典顺序从小到大排列在一个容器中，那么数组的 下一个排列 就是在这个有序容器中排在它后面的那个排列。如果不存在下一个更大的排列，那么这个数组必须重排为字典序最小的排列（即，其元素按升序排列）。

  • 例如，arr = [1,2,3] 的下一个排列是 [1,3,2] 。
  • 类似地，arr = [2,3,1] 的下一个排列是 [3,1,2] 。
  • 而 arr = [3,2,1] 的下一个排列是 [1,2,3] ，因为 [3,2,1] 不存在一个字典序更大的排列。

给你一个整数数组 nums ，找出 nums 的下一个排列。

必须** 原地 **修改，只允许使用额外常数空间。

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
class Solution {
    public void nextPermutation(int[] nums) {
        //从后到前遍历，找到一个非降序的，并替换
        if (nums.length <= 1){
            return;
        }
        // 1、i从字符串末尾向前进行遍历，找到一个字符s[i] < s[i + 1]
        int i = nums.length - 2;
        while (i >= 0 && nums[i] >= nums[i + 1]) {
            i--;
        }
        if (i >= 0) {
            // 2、 j从字符串末尾向前进行遍历，找到一个字符s[j] > s[i]
            int j = nums.length - 1;
            while (j > i && nums[j] <= nums[i]) {
                j--;
            }
            // 3、i和j进行交换
            int t = nums[i];
            nums[i] = nums[j];
            nums[j] = t;
        }
        // 4、对i位置以后的字符进行逆序（不包括i）
        int l = i + 1;
        int r = nums.length - 1;
        while (l < r) {
            int t = nums[l];
            nums[l] = nums[r];
            nums[r] = t;
            l++;
            r--;
        }
    }
}