Concise C++ solution 12ms O(nlgn) solution with detailed explain


  • 2

    思路:2次遍历O(n),从后往前,如果数组不是一路降序,一定可以找到一个位置破坏了排序,这第一个位置就是我们关心的。例如:[2,1,3,5,4,3,2,1,0], 左数第一个3就是从右边数第一个破坏顺序的元素,将之与其右边最靠右的比它大的元素(4)交换,然后再将4之后的元素排序O(nlgn),就得到了结果。无独有偶,发现我的思路和别人是一样的.

    Traverse the array twice backwards using two pointers

    First time: to find if the array is in descending order, if yes, reverse the array; otherwise, you can find the first element to the right that breaks the descending order, mark the position of it as turn;

    Second time: to find the first element i to the right that's smaller than nums[turn], then swap them, and reorder the elements to the right of position turn.

    I found later this idea was well explained here:

    https://leetcode.com/submissions/detail/54604251


    class Solution {
    public:
        void nextPermutation(vector<int>& nums) {
            int turn = -1;
            // Search backwards to find the first position 'turn' that breaks the order
            // e.g. [4,2,0,2,3,2,0] <-- search backwards
            // 0 -> 2 -> 3 -> 2 (found it! 0 < 2 < 3 >2)
            for(int i = nums.size() - 1; i > 0; i--){
                if(nums[i] > nums[i - 1]) {
                    turn = i - 1;  
                    break;
                }
            }
            // Search backwards again, find the first element that is larger than nums[turn], then swap
            // then sort the array after nums[turn]
            int i = nums.size();
            while(i--){
                // if turn equals it's initial value, means the vector is descending order
                if(turn == -1 || nums[turn] < nums[i]){
                    if(turn >= 0) swap(nums[turn], nums[i]);
                    sort(nums.begin() + turn + 1, nums.end());
                    break;
                }
            }
            return;
        }
    };

Log in to reply
 

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