O(n) java solution with comments, 250ms


  • 0
    M
    public String getPermutation(int n, int k) {
        if(n==1){
            return "1";
        }
    	int frac=1;
    	
    	// a[i] records how many (n-1-i)!permutuations we need
    	// eg. if n=8, a[0],a[1],a[2] means how many 7! 6! and 5! permutaions we need
    	// the idea is that a[0]+a[1]+...+a[n-1]=k
    	int[] a=new int[n];
    	for(int i=1;i<n;i++){
    		frac*=i;
    	}
    	int finish=0;
    	for(int i=0;i<n-1;i++){
    		a[i]=(k-k%frac)/frac;
    		k-=a[i]*frac;
    		
    		// if we already add permutations up to k, we can stop processing the remaining permutations
    		if(k==0){
    		    finish=i;
    		    break;
    		}
    		
    		frac/=n-1-i;
    	}
        TreeSet<Integer> ts=new TreeSet<>();
        for(int i=1;i<=n;i++){
            ts.add(i);
        }
        StringBuffer sb=new StringBuffer();
        
        for(int i=0;i<finish;i++){
            int mth;
            mth=mthEle(a[i]+1,ts);
            a[i]=mth;
            ts.remove(mth);
            sb.append(a[i]);
        }
        
        // note that on the final bit, we need to substarct by 1, because the following (n-finish-1)! will account for 1 
        int fin=mthEle(a[finish],ts);
        a[finish]=fin;
        ts.remove(fin);
        sb.append(a[finish]);
        
        // get the largest permutation of the remaining, i.e, permute them in the descending order
        Iterator<Integer> it=ts.descendingIterator();
        while(it.hasNext()){
            sb.append(it.next());
        }
        return sb.toString();
        
        
        
    }
    public int mthEle(int m,TreeSet<Integer> ts){
        //return the mth element which is larger than the smallest element in ts
        Iterator<Integer> it = ts.iterator();
        if(m==0){
            return ts.first();
        }
        int i = 0;
        Integer current = null;
        while(it.hasNext() && i < m) {
            current = it.next();
            i++;
        }
        return current;
    }

  • 0
    T

    Does the remove operation of TreeSet take O(log n) time? Because it is backed by a balanced tree. Therefore it is actually O(nlog n) ?


Log in to reply
 

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