The shortest solution C++.


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

    And realisation without standart function next_permutation:

    class Solution {
    public:
        void nextPermutation(vector<int>& nums) {
            int maxx = -1e9;
            auto start_iter = nums.end();
            for (auto iter = nums.end() - 1; iter >= nums.begin(); --iter) {
                if (*iter >= maxx) {
                    maxx = *iter;
                } else {
                    start_iter = iter;
                    break;
                }
            }
            if (start_iter == nums.end()) {
                reverse(nums.begin(), nums.end());
                return;
            }
            for (auto iter = nums.end() - 1; iter >= nums.begin(); --iter) {
                if (*start_iter < *iter) {
                    swap(*start_iter, *iter);
                    break;
                }
            }    
            reverse(start_iter + 1, nums.end());
            return;
        }
    };
    

    Time O(n), memory O(1).
    Idea : 1) find first position wich must changed,

    1. find what must be on that position, and swap that
    2. all elements after start_iter sorted descending, and we must sort it ascending. We can do it in O(n), using reverse.

  • 0

    That's not the shortest, here is one that's two characters shorter.


Log in to reply
 

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