Concise nonrecursive c++ 0ms solution


  • 0
    Q
    // The basic idea is to put numbers in 3 categories: before, after, or equal.
    // The category checking  can be optimized as only "equal" can change to "before" or "after".  
    // Once is in "before" or "after", it will stay in that category.
    class Solution {
    public:
        int findKthNumber(int n, int k) {
            
            string res;
        	string nstr = to_string(n);
        	
        	int dCounter = 0;
        	for (int i = 0; i<nstr.length(); i++)
        		dCounter += pow(10,i);
        
        	int pos = 0;
        	int hist[57+1] = {};
        
        	while (k>0)
        	{
        		k--; //tricky, skip the current number 
        
        		if ( res==nstr.substr(0,pos) )
        		{
        			int sum = 0;
        			hist[nstr[pos]] = 0;
        			for (char d = res.empty()?'1':'0'; d <= '9'; d++)
        			{
        				if (d< nstr[pos]) hist[d] = dCounter;
        				else if ( d>nstr[pos] )  hist[d] = dCounter / 10;
        				sum += hist[d];
        			}
        			n -= sum;
        			hist[nstr[pos]] =n;
        			n--; //exclude the current number
        		}
        		else if ( res<nstr.substr(0, pos) )
        		{
        			for (char d = '0'; d <= '9'; d++)
        				hist[d] = dCounter;
        		}
        		else
        		{
        			for (char d = '0'; d <= '9'; d++)
        				hist[d] = dCounter/10;
        		}
        
        		char d = '0';
        		while (k>=hist[d]) k -= hist[d++];
        
        		res.append(1, d);
        
        		pos++;
        		dCounter /= 10;
        
        	}
        
        	return atoi(res.c_str());
        }
    };
    

Log in to reply
 

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