I think the complexity can be O(n*lgn)


  • 0
    C
    public class Solution {
    public void nextPermutation(int[] num) {
        int i,j;
        waiceng:
        for(i=num.length-2;i>=0;i--)
        {
            int s=i+1,e=num.length-1;
            while(s<=e-1)
            {
                int t =(s+e+1)/2;
                if(num[t]>num[i])
                    s=t;
                else
                    e=t-1;
            }
            if(num[e]>num[i])
            {
                int t = num[i];
                num[i]=num[e];
                num[e]=t;
                break;
            }
        }
     
        int s = i+1;int e=num.length-1;
        while(s<e)
        {
            int t = num[s];
            num[s]=num[e];
            num[e]=t;
            s++;e--;
        }
    }
    

    }


  • 0
    Z

    Diao's! It's you! There is an O(N) complexity algorithm.
    class Solution {
    public:
    void nextPermutation(vector<int> &num) {
    if(num.size()==0)return;
    int i;
    for(i=num.size()-2;i>=0;--i)
    {
    if(num[i]<num[i+1])
    {
    break;
    }
    }
    if(i>=0)
    {
    for(int j=num.size()-1;j>i;--j)
    if(num[j]>num[i])
    {
    swap(num[i],num[j]);
    break;
    }
    }
    reverse(num.begin()+i+1,num.end());
    }
    };


Log in to reply
 

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