首页 > 代码库 > [C++]LeetCode: 79 Next Permutation （下一个排列，常见面试题）

[C++]LeetCode: 79 Next Permutation （下一个排列，常见面试题）

2024-10-28 22:51:02   208人阅读

题目：

Implement next permutation, which rearranges numbers into the lexicographically next greater permutation of numbers.

If such arrangement is not possible, it must rearrange it as the lowest possible order (ie, sorted in ascending order).

The replacement must be in-place, do not allocate extra memory.

Here are some examples. Inputs are in the left-hand column and its corresponding outputs are in the right-hand column.
1,2,3 → 1,3,2
3,2,1 → 1,2,3
1,1,5 → 1,5,1

思路：所谓一个排列的下一个排列的意思就是，在这一个排列和下一个排列之间没有其他的排列。这就要求我们这一个排列和下一个排列拥有尽可能长的共同前缀，也即变化限制在尽可能短的后缀上。

举个例子：

比如序列，7 8 6 9 8 7 2； 7 8 7 9 8 6 2； 7 8 7 2 6 8 9；

  先看前面2排的话，可以看出来第二排是比第一排要大的，参考字符串比较大小的问题。那么第2个排列是不是第一个排列的下一个排列呢。很明显不是，第3个排列才是， 那么如何获取到下一个排列呢。
步骤比较简单：假设数组大小为 n
        1.从后往前，找到第一个 A[i-1] < A[i]的。也就是第一个排列中的  6那个位置，可以看到A[i]到A[n-1]这些都是单调递减序列。9,8,7，2递减
        2.从 A[n-1]到A[i]中找到一个比A[i-1]大的值（也就是说在A[n-1]到A[i]的值中找到比A[i-1]大的集合中的最小的一个值）。从末尾找到第一个大于i 的元素，记为 j。即7。
        3.交换 这两个值，并且把A[n-1]到A[i]排序，从小到大。由于j是第一个大于i的元素，则交换后，之后仍然满足递减排列，直接reverse得到升序排列。8 6 4 3 2按照递增重新排列。
        4. 如果某个排列没有比他大的下一个排列（即该排列是递增有序的），翻转整个排列，得到最小的排列。
技术分享
Attention：
1. 定位到i 之后，需要找到第一个大于i的 元素 j，等于都不可以，一定要满足大于。（等于交换没有意义）
//找到i-1之后第一个大于num[i-1]的数字，并交换
                int j = n - 1;
                while(num[i] >= num[j]) j--;
                swap(num[i], num[j]);
2.由于j是第一个大于i的元素，所以交换后，ii开始到末尾，仍然满足递减顺序，直接reverse得到递增排列。注意是从ii开始翻转。
//交换后，仍然是降序排列。
reverse(num.begin() + ii, num.end());
3. 简单记忆步骤
  • 从最尾端开始往前寻找两个相邻的元素，两者满足i < ii（令第一个元素为i，第二个元素为ii）
  • 如果没有找到这样的一对元素则，表明当前的排列是最大的，没有下一个大的排列
  • 如果找到，再从末尾开始找出第一个大于i的元素，记为j                                  
  • 交换元素i, j，再将ii后面的所有元素颠倒排列(包括ii)
  • 如果某个排列没有比他大的下一个排列（即该排列是递减有序的），调用这个函数还是会把原排列翻转，即得到最小的排列
复杂度：O(N)
AC Code:
class Solution {
public:
    void nextPermutation(vector<int> &num) {
        int n = num.size();
        if(n == 1) return;
        
        for(int i = n-2, ii = n-1; i >= 0; i--, ii--)
        {
            //找到第一组相邻的降序组合
            if(num[i] < num[ii])
            {
                //找到i-1之后第一个大于num[i-1]的数字，并交换
                int j = n - 1;
                while(num[i] >= num[j]) j--;
                swap(num[i], num[j]);
                //交换后，仍然是降序排列。
                reverse(num.begin() + ii, num.end());
                return;
            }
        }
        //如果排列是递减有序的，翻转整个数组
        reverse(num.begin(), num.end());
        return;
    }
};




[C++]LeetCode: 79 Next Permutation （下一个排列，常见面试题）


联系
我们