386. Lexicographical Numbers

Given an integer n, return 1 - n in lexicographical order.

For example, given 13, return: [1,10,11,12,13,2,3,4,5,6,7,8,9].

Please optimize your algorithm to use less time and space. The input size may be as large as 5,000,000.

登录后复制

      
      

       
       class Solution {
       
       
    private List<Integer> result;
       
       
    private int n;
       
       
    public List<Integer> lexicalOrder(int n) {
       
       
        this.result = new ArrayList<Integer>();
       
       
        this.n = n;
       
       
        solve(1);
       
       
        return result;
       
       
    }
       
       
    private void solve(int m) {
       
       
        result.add(m);
       
       
        if (m * 10 <= n) solve(m * 10);
       
       
        if (m < n && m % 10 < 9) solve(m + 1);
       
       
    }
       
       
}
      
      
      
      

       
       
1.
       
       
2.
       
       
3.
       
       
4.
       
       
5.
       
       
6.
       
       
7.
       
       
8.
       
       
9.
       
       
10.
       
       
11.
       
       
12.
       
       
13.
       
       
14.
       
       
15.