C++ Solution using map


  • 0
    A

    class Solution {
    public:
    void form_fact(unordered_map<int,int>& fact,int start,int n,int pd) {
    if(start>n) return;
    pd*=start;
    fact[start]=pd;
    form_fact(fact,start+1,n,pd);
    }
    int get_val(set<int>& track,int index) {
    for(int i : track) {
    if(index == 0) return i;
    index--;
    }
    return 0;
    }
    string traverse(int k,set<int>& track,int n,unordered_map<int,int>& fact) {
    if(n==1) return to_string(track.begin());
    int options = track.size();
    int each = fact[n]/options;
    //cout << options << "\t" << each <<"\t"<<k<< endl;
    int index = (k-1)/each;
    int val = get_val(track,index);
    track.erase(val);
    return to_string(val)+traverse(k-index
    each,track,n-1,fact);
    }
    string getPermutation(int n, int k) {
    set<int> track;
    unordered_map<int,int> fact;
    form_fact(fact,1,n,1);
    for(int i=1;i<=n;i++) track.insert(i);
    return traverse(k,track,n,fact);
    }
    };


Log in to reply
 

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