C++ 9ms O(n) solution


  • 0
    A
    class Solution {
    public:
        void nextPermutation(vector<int>& nums) {
            int i,n=nums.size(),flag,flag1,min=99999;
            if(n==2) swap(nums[0],nums[1]);
            if(n>=3)
            {
                for(i=n-1;i>=1;i--)
                {
                    if(nums[i-1]<nums[i]) break;
                }
                flag=i-1;
                if(flag!=-1)
                {
                    for(i=flag+1;i<n;i++)
                    {
                        if(min>nums[i]&&nums[i]>nums[flag])
                        {
                            min=nums[i];
                            flag1=i;
                        }
                    }
                    swap(nums[flag],nums[flag1]);
                    sort(nums.begin()+flag+1,nums.end()); 
                }
                else 
                {
                    reverse(nums.begin(),nums.end());
                }
            }
          }
    };

  • 0
    Z

    Hi! The solution is not O(n) but O(n*log(n)), because of sorting. Moreover it may become O(n^2) If the array is sorted in non-ascending order already


Log in to reply
 

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