sample java solution, O(n), non-recursion


  • 0
    Q
    	//sort the numbers from 1 to n by Lexicographical order
        public List<Integer> lexicalOrder(int n) {
            List<Integer> res = new ArrayList<Integer>();
            
            //1、start by 1
            int cur = 1;
            
            while(res.size()<n){
            	res.add(cur);
            
            	//2、if cur*10 less than n, we first put cur*10,that means we first put 1 10 100..., 2,20,200 and so on
            	while(cur*10<=n && res.size()<n){
            		cur = cur*10;
            		res.add(cur);
            	}
            	
            	//3、increase cur by 1, until the last number of cur is '9'
            	while((res.size()<n && (cur+1)%10!=0) && cur+1<=n){
            		cur++;
            		res.add(cur);        		
            	}
            	
            	//stop by 'cur+1<=n'
            	if(cur>=n){
            		cur = cur/10+1;
            	}else{  //stop by the last number of cur is '9'
            		cur = (cur+1)/10;
            	}
            	
            	//4、remove '0' in the cur, for example '199'->'2'
            	while(cur%10==0){
            	    cur /= 10;
            	}
            }
            return res;
        }
    

Log in to reply
 

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