Welcome to Subscribe On Youtube

386. Lexicographical Numbers

Description

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

DFS.

• Java
• C++
• Python
• Go
• Javascript
• RenderScript
• TypeScript

• 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;
      }
  }
  

• 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;
      }
  };
  

• 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
  
  

• func lexicalOrder(n int) []int {
  	var ans []int
  	v := 1
  	for i := 0; i < n; i++ {
  		ans = append(ans, v)
  		if v*10 <= n {
  			v *= 10
  		} else {
  			for v%10 == 9 || v+1 > n {
  				v /= 10
  			}
  			v++
  		}
  	}
  	return ans
  }
  

• /**
   * @param {number} n
   * @return {number[]}
   */
  var lexicalOrder = function (n) {
      let ans = [];
      function dfs(u) {
          if (u > n) {
              return;
          }
          ans.push(u);
          for (let i = 0; i < 10; ++i) {
              dfs(u * 10 + i);
          }
      }
      for (let i = 1; i < 10; ++i) {
          dfs(i);
      }
      return ans;
  };
  
  

• impl Solution {
      fn dfs(mut num: i32, n: i32, res: &mut Vec<i32>) {
          if num > n {
              return;
          }
          res.push(num);
          for i in 0..10 {
              Self::dfs(num * 10 + i, n, res);
          }
      }
  
      pub fn lexical_order(n: i32) -> Vec<i32> {
          let mut res = vec![];
          for i in 1..10 {
              Self::dfs(i, n, &mut res);
          }
          res
      }
  }
  
  

• function lexicalOrder(n: number): number[] {
      const ans: number[] = [];
      let v = 1;
      for (let i = 0; i < n; ++i) {
          ans.push(v);
          if (v * 10 <= n) {
              v *= 10;
          } else {
              while (v % 10 === 9 || v === n) {
                  v = Math.floor(v / 10);
              }
              ++v;
          }
      }
      return ans;
  }
  
  

All Problems

All Solutions