386

386. Lexicographical Numbers (Medium)

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.

Companies:
Amazon, Baidu, eBay, Bloomberg

Solution 1.

// OJ: https://leetcode.com/problems/lexicographical-numbers/
// Author: github.com/lzl124631x
// Time: O(N)
// Space: O(1)
class Solution {
public:
    vector<int> lexicalOrder(int n) {
        int x = 1;
        vector<int> ans;
        while (ans.size() < n) {
            ans.push_back(x);
            if (x * 10 <= n) {
                x *= 10;
            } else {
                if (x + 1 > n) {
                    x /= 10;
                    ++x;
                } else ++x;
                while (x % 10 == 0) x /= 10;
            }
        }
        return ans;
    }
};