Question

Formatted question description: https://leetcode.ca/all/386.html

 386	Lexicographical Numbers

 Given an integer n, return from 1 to 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.

Algorithm

Traverse by single digit. Before traversing the next single digit, first traverse the tens digit. The high digit of the tens digit is the previous single digit.

As long as the multi-digit number does not exceed n, it can be traversed all the time. If it exceeds, we divide by 10, and then add 1.
If a lot of 0s are formed at the end after adding 1, then we need to use a while loop to remove all 0s, and then continue to calculate.

Example, for n=113

1,
    10,
        100, 101, 102, 103, 104, 105, 106, 107, 108, 109,
    11,
        110, 111, 112, 113,
    12, 13, 14, 15, 16, 17, 18, 19,
2,
    20, 21, 22, 23, 24, 25, 26, 27, 28, 29,
3,
    30, 31, 32, 33, 34, 35, 36, 37, 38, 39,
4,
    40, 41, 42, 43, 44, 45, 46, 47, 48, 49,
5,
    50, 51, 52, 53, 54, 55, 56, 57, 58, 59,
6,
    60, 61, 62, 63, 64, 65, 66, 67, 68, 69,
7,
    70, 71, 72, 73, 74, 75, 76, 77, 78, 79,
8,
    80, 81, 82, 83, 84, 85, 86, 87, 88, 89,
9,
    90, 91, 92, 93, 94, 95, 96, 97, 98, 99
...

Code

Java

import java.util.ArrayList;
import java.util.List;

public class Lexicographical_Numbers {

    public static void main(String[] args) {
        Lexicographical_Numbers out = new Lexicographical_Numbers();
        Solution s = out.new Solution();

        System.out.println(s.lexicalOrder(113));
    }


    class Solution {



        public List<Integer> lexicalOrder(int n) {

            List<Integer> result = new ArrayList<>();
            for (int i = 1; i <= 9; ++i) {
                helper(i, n, result);
            }
            return result;
        }

        private void helper(int cur, int n, List<Integer> result) {
            if (cur > n) {
                return;
            }
            result.add(cur);
            for (int i = 0; i <= 9; ++i) {
                if (cur * 10 + i <= n) {
                    helper(cur * 10 + i, n, result);
                }
            }
        }
    }
}

// OJ: https://leetcode.com/problems/lexicographical-numbers/
// 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;
    }
};

class Solution:
    def lexicalOrder(self, n: int) -> List[int]:
        v = 1
        ans = []
        for i in range(n):
            ans.append(v)
            if v * 10 <= n:
                v *= 10
            else:
                while v % 10 == 9 or v + 1 > n:
                    v //= 10
                v += 1
        return ans

############

class Solution(object):
  def lexicalOrder(self, n):
    """
    :type n: int
    :rtype: List[int]
    """
    ans = [0] * n
    self.cnt = 0
    self.dfs(ans, n, 0)
    return ans

  def dfs(self, ans, n, pre):
    if self.cnt == n or pre > n:
      return
    if pre * 10 > n:
      return
    for i in range(0, 10):
      cur = pre * 10 + i
      if cur == 0:
        continue
      if self.cnt == n or cur > n:
        return
      ans[self.cnt] = cur
      self.cnt += 1
      self.dfs(ans, n, cur)

386 - Lexicographical Numbers

Question

Algorithm

Code

All Problems

All Solutions

Welcome to Subscribe On Youtube

Question

Algorithm

Code

All Problems

All Solutions