publicclassLexicographicalNumbers{ /** * 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. * * @param n * @return */ publicstatic List<Integer> lexicalOrder(int n){ List<Integer> res = new LinkedList<Integer>(); for (int i=1; i<10; i++){ dfs(res, n, i); } return res; }
publicstaticvoiddfs(List<Integer> res, int n, int cur){ if (cur > n) return ; res.add(cur); for (int i=cur*10; i<cur*10+10; i++){ dfs(res, n, i); } return ; } publicstaticvoidmain(String[] args){ for (int c: lexicalOrder(19)){ System.out.println(c); } } }