9 Lines of C++ code with Comments


  • 42
    S
    class Solution {
    public:
        void nextPermutation(vector<int> &num) 
        {
            if (num.empty()) return;
            
            // in reverse order, find the first number which is in increasing trend (we call it violated number here)
            int i;
            for (i = num.size()-2; i >= 0; --i)
            {
                if (num[i] < num[i+1]) break;
            }
            
            // reverse all the numbers after violated number
            reverse(begin(num)+i+1, end(num));
            // if violated number not found, because we have reversed the whole array, then we are done!
            if (i == -1) return;
            // else binary search find the first number larger than the violated number
            auto itr = upper_bound(begin(num)+i+1, end(num), num[i]);
            // swap them, done!
            swap(num[i], *itr);
        }
    };
    

    You might need to think for a while why this would work.


  • 0
    R

    very clear. work like a charm


  • 0
    E

    class Solution {
    public:

    void nextPermutation(vector<int>& nums) {
    	if(!nums.size() || nums.size() == 1)
    		return;
    	
        int i = nums.size() - 1;
    	for(; i - 1 >= 0 && nums[i - 1] >= nums[i]; --i);
    	if(i == 0)
    	{
    		for(int front = 0, back = nums.size() - 1; front < back; swap(nums[front++], nums[back--]));
    	}
    	else if(i - 1 >= 0)
    	{
    		int pivot = --i;
    		for(;i + 1 < nums.size() && nums[pivot] < nums[i + 1]; ++i);
    		swap(nums[pivot], nums[i]);
    		for(int front = pivot + 1, back = nums.size() - 1; front < back; swap(nums[front++], nums[back--]));
    	}
    }
    

    };


  • 0
    S

    @ShadowGIraffe
    You use upper_bound() which we will use if list/vector is sorted. Am I missing something?


  • 0
    C

    @simemon
    that part of list is already sorted(at first it was degressive, and then we reversed it, so it become ascending ).


  • 0
    W

    @ShadowGIraffe 没学过C++的觉得好高大上啊


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.