leetcode_Next Permutation笔记

        题意：找出比当前排序大一号的排序，如果当前排序就是最大排序，那么将它重拍成最小排序。

原题

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,23,2,1 → 1,2,31,1,5 → 1,5,1

代码

class Solution {
public:
    void nextPermutation(vector<int>& nums) {
        for(int i = nums.size()-1; i >= 1; i--){
            if(nums[i] > nums[i-1]){
                int index = nums.size()-1;
                int min = INT_MAX;
                for(int j = i; j < nums.size(); j++){
                    int temp = nums[j] - nums[i-1];
                    if(temp > 0 && temp < min){
                        min = temp;
                        index = j;
                    }
                }
                std::swap(nums[i-1], nums[index]);
                std::sort(nums.begin() + i, nums.end());
                break;
            } else{
                if(i == 1){
                    std::sort(nums.begin(), nums.end());
                }
            }
        }
    }
};

分析

        把序列想象成一个数字，交换要尽量发生在低位，并且要与之前（个位方向）的比自身大的最小值进行交换。

        深刻理解题目之后，思想很简单（主要是对题目的理解），按照如下规则就可以写出代码

        1.当nums[i-1]<nums[i]时才发生交换

        2.nums[i-1]仅与他右边比他大的值中的最小值进行交换

        3.交换完之后，右侧序列需要升序排序

        OK，See You Next Chapter!