力扣31题：下一个排列

  • 该操作直接在STL中有实现，支持重复元素；
  • 交换可以用swap函数；
  • 主要思路为从右往左数到第一个逆序对，逆序对的前者与之后的所有序列中比他大的最小值进行交换。最后把这一段进行reverse就可。
  • 如果该序列已经为最大值，则reverse整个序列。
class Solution {
public:
    //该方法支持序列中存在重复元素，且在 C++ 的STL中被采用：
    // next_permutation(nums.begin(), nums.end());
    void nextPermutation(vector<int>& nums) {
        int n = nums.size();
        for(int i = n-1 ; i >= 1; --i){
            if(nums[i] > nums[i-1]){
                int j = i;
                for(; j+1 < n; ++j){
                    if(nums[j+1] <= nums[i-1]) break;    //不加等号： 错误[1,5,1]
                }
                //下面三行等效于： swap(nums[i-1],nums[j]);
                int t = nums[j];
                nums[j] = nums[i-1];
                nums[i-1] = t;
                reverse(nums.begin() + i,nums.end());
                return;
            }
        }
        reverse(nums.begin() , nums.end());
    }
};

版权声明：本文为jinjin-2018原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。
本文链接：https://www.cnblogs.com/jinjin-2018/p/13954399.html