Accepted c++ solution, 12ms, as fast as std::next_permutation, easy understand.


  • 0

    For example, if the permutation is [1,4,6,5,3,2], search from right to left to find the first index which meet
    the condition nums[i] < nums[i + 1], we can get nums[1] < nums[2], so idx1 = 1, then search from right to left again to find the first index which meet the condition nums[i] > nums[idx1], we can get nums[3] > nums[1], so idx2 = 3, after swap nums[idx1] and nums[idx2], the permutation is [1,5,6,4,3,2] now, and the sub permutation after idx1 is in descending order, here is [6,4,3,2], we should turn it into ascending order.

    class Solution {
    public:
        void nextPermutation(std::vector<int> &nums) {
            int len = static_cast<int>(nums.size());
            if (len < 2)
                return;
            int idx1 = -1, idx2;
    		// search from right to left to find the first index which meet the condition nums[i] < nums[i + 1]
            for (int i = len - 2; i >= 0; --i)
                if (nums[i] < nums[i + 1]) {
                    idx1 = i;
                    break;
                }
            if (idx1 != -1) {
    			// search from right to left again to find the first index which meet the condition nums[i] > nums[idx1]
                for (int i = len - 1; i != idx1; --i)
                    if (nums[i] > nums[idx1]) {
                        idx2 = i;
                        break;
                    }
                std::swap(nums[idx1], nums[idx2]);
            }
    		// turn the sub permutation after idx1 into ascending order
            ++idx1;
            idx2 = len - 1;
            while (idx1 < idx2)
                std::swap(nums[idx1++], nums[idx2--]);
        }
    };
    

    Use STL function std::next_permutation, also 12ms:

    class Solution {
    public:
        void nextPermutation(std::vector<int> &nums) {
    	    std::next_permutation(nums.begin(), nums.end());
        }
    };
    

Log in to reply
 

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