C++ iterative 4ms solution


  • 1
    N
    string getPermutation(int n, int k) {
    	int coeff[n] = {1};     // 1, 2, 6, 24, .., n!
    	for (int i = 1; i<n-1; i++) coeff[i] = coeff[i - 1] * (i + 1);
    	k--;
    
    	string ret;
    	vector<int> num;
    	for (int i = 1; i<=n; i++) num.push_back(i);    // 1, 2, 3, .., n
    	
    	// calculate offset and remove the item.
    	for (int i = n; i>1; i--)
    	{
    		int off_coeff = i - 2;
    		int off_num = k / coeff[off_coeff];
    		ret += to_string(num[off_num]);
    		num.erase(num.begin() + off_num);
    		k = k%coeff[off_coeff];
    	}
    	ret += to_string(num[0]);
    
    	return ret;
    }

Log in to reply
 

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