386 - Lexicographical Numbers

Given an integer n, return all the numbers in the range [1, n] sorted in lexicographical order.

You must write an algorithm that runs in O(n) time and uses O(1) extra space. 

Example 1:

Input: n = 13
Output: [1,10,11,12,13,2,3,4,5,6,7,8,9]

Example 2:

Input: n = 2
Output: [1,2]

 Constraints:

• 1 <= n <= 5 * 104

Solutions

C++

• class Solution {
  public:
      vector<int> lexicalOrder(int n) {
          vector<int> ans;
          int v = 1;
          for (int i = 0; i < n; ++i) {
              ans.push_back(v);
              if (v * 10 <= n)
                  v *= 10;
              else {
                  while (v % 10 == 9 || v + 1 > n) v /= 10;
                  ++v;
              }
          }
          return ans;
      }
  };

JAVA

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