Leetcode31. Next Permutation(字典序排列)

题目描述

• 题目来自于leetcode 31，详细描述如下：

  
  
• 大意是给定一个字符串序列，输出他下一个字典序序列

代码如下：

void nextPermutation(vector<int>& nums) {
        int i = nums.size() - 1, k = i;
        while (i > 0 && nums[i - 1] >= nums[i])    i--;
       
        for (int j = i; k > j; j++, k--)     swap(nums[j], nums[k]);
        
        if (i > 0) {
            k = i--;
            while (nums[i] >= nums[k])     k++;
            swap(nums[i], nums[k]);
        }
        
    }

分析

1. 先倒叙查找，找到一个点i，保证i及其后面的所有字符组成的子串字典序最大
2. 翻转这个子串
3. 这个子串前面的字符C若是整个串的首字符，则返回，否则。将c与子串里面字典序次于c的字符进行交换（子串的字典序已是最小）