a 10-line C++ implementation of the classic algorithm


  • 0
    L

    With upper_bound() within a for-loop, it's still O(n). Do you know why?

        void nextPermutation(vector<int>& nums) {
            for (auto i=nums.rbegin(); i!=nums.rend(); ++i) {
                auto j = upper_bound(nums.rbegin(), i, *i);
                if (j != i) {
                    swap(*i, *j);
                    reverse(nums.rbegin(), i);
                    return;
                }
            }
            reverse(nums.rbegin(), nums.rend());
        }
    '''

Log in to reply
 

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