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.

Solution:

The result should return a list of n numbers. So we use a for loop to iterate n times.

In each round, we add the current number x to the list. And we do the following:

1. If x * 10 <= n, it means that x * 10 will be the next number in lexicographical order. (the next number of 1 is 10.)

2. If x >= n, we cannot add 1 to it because it will be invalid. So we cut its last digit, as x = x / 10; (if n is 13, and x == 13, we need to turn it back to 1 and process step 3.)

3. Add 1 to x and it is now a candidate for the next lexicographical order number.

4. Check if this candidate has trailing zeroes. If so, remove all the trailing zeroes. (the next number of 1999 is 2, instead of 2000.)



Code:

public class Solution {
    public List<Integer> lexicalOrder(int n) {
        List<Integer> result = new ArrayList<>();
        int curr = 1;
        for (int i = 0; i < n; i++) {
            result.add(curr);
            if (curr * 10 <= n) {
                curr *= 10;
            }
            else {
                if (curr >= n) {
                    curr /= 10;
                }
                curr++;
                while (curr % 10 == 0) {
                    curr /= 10;
                }
            }
        }
        return result;
    }
}