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.

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

All Problems

All Solutions