80ms beats 100%


  • 0
    I

    Improved recursive solution

    public class Solution {
        public List<Integer> lexicalOrder(final int n) {
            final int maxHigh = n/10;
            
            final Integer[] ans = new Integer[n];
            final int[] index = new int[1];
            
            for(int i=1; i<=9 && i<= n; i++) {
                ans[index[0]++] = i;
                
                if(i <= maxHigh) {
                    compute(ans, index, n, maxHigh, (i<<3) + (i<<1));
                }
            }   
            
            return Arrays.asList(ans);
        }
        
        private void compute(final Integer[] ans, final int[] index, final int n, final int maxHigh, final int high) {
            for(int i=0; i<=9; i++) {
                final int temp = high + i;
    
                if(temp > n) return;
                
                ans[index[0]++] = temp;
                
                if(temp <= maxHigh) {
                    compute(ans, index, n, maxHigh, (temp<<3) + (temp<<1));
                }
            }
        }
    }
    

Log in to reply
 

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