My solution in cpp, fairly concise


  • 1
    S

    My thought is:

    1. store the available numbers, store the n factor values
    2. go through each char in the target string, fill it with expected value directly.
    3. the expected value is calculated as t = number[(k-1)/(n-1)!], if k is counted down to 0, t should be end of the available numbers, then k update to k%(n-1)!
      e.g. if n=3, k=2,
      the first expected value is indexed at 1/2 = 0 in available numbers (1, 2, 3), t = 1. k is updated to 0
      the second expected value is indexed at 1 since k=0 in available numbers: (2, 3), t = 3. k is updated to 0
      the third expected value is indexed at 0 in available numbers (2), t = 0, k is still 0.

    The code is:

    string getPermutation(int n, int k) {
        if (n <= 0 || k <= 0) return "";
        vector<int> factor(n + 1, 1);
        vector<int> array(n, 1);
        string s(n, '0');
        
        for (int i = 1; i < n; i++) {
            factor[i] = factor[i - 1] * i;
            array[i] = i + 1;
        }
        
        int j = n;
        for (int i = 0; i < n; i++) {
            int count = k ? (k-1)/factor[j-1] : j - 1;
            k = k%factor[j-1];
            if (count > n) break;
            s[i] += array[count];
            array.erase(array.begin() + count);
            j--;
        }
        
        return s;
    }
    

    The time complexity should be O(n^2) since erase element from array takes n. space complexity is O(n)


  • 0
    R

    My java solution with a similar idea.

    public class Solution {
        String result="";
        int[] array;
        public String getPermutation(int n, int k) {
    		array=new int[n+1];
    		
    		for (int i=0;i<n;i++)
    			array[i]=i+1;
    		array[n]=0;
    		
    		int perm=1;		
    		for (int i=1;i<=n;i++)
    			perm*=i;
    					
        	doPermutationHelper(array,perm,n,k);
        	return result;
            
        }
        private void doPermutationHelper(int[] a,int perm,int n,int k){
            if (n==1) {
                result+=String.valueOf(a[0]);
                return;
            }
            
            perm/=n;
            int i=(k-1)/perm;
            result+=String.valueOf(a[i]);
            while (i<n-1)
            	a[i++]=a[i];
            doPermutationHelper(a,perm,n-1,(k-1)%perm+1);
        }
    }

Log in to reply
 

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