README_EN.md

386. Lexicographical Numbers

中文文档

Description

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

 

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

 

Follow up: Could you optimize your solution to use O(n) runtime and O(1) space?

Solutions

DFS.

Python3

class Solution:
    def lexicalOrder(self, n: int) -> List[int]:
        res = []

        def dfs(i, n):
            if i > n:
                return
            res.append(i)
            for j in range(10):
                dfs(i * 10 + j, n)

        for i in range(1, 10):
            dfs(i, n)
        return res

Java

class Solution {
    public List<Integer> lexicalOrder(int n) {
        List<Integer> res = new ArrayList<>();
        for (int i = 1; i < 10; ++i) {
            dfs(res, i, n);
        }
        return res;
    }

    private void dfs(List<Integer> res, int i, int n) {
        if (i > n) {
            return;
        }
        res.add(i);
        for (int j = 0; j < 10; ++j) {
            dfs(res, i * 10 + j, n);
        }
    }
}

C++

class Solution {
public:
    vector<int> lexicalOrder(int n) {
        vector<int> res;
        for (int i = 1; i < 10; ++i)
        {
            dfs(res, i, n);
        }
        return res;
    }

    void dfs(vector<int> &res, int i, int n) {
        if (i > n)
            return;
        res.push_back(i);
        for (int j = 0; j < 10; ++j)
        {
            dfs(res, i * 10 + j, n);
        }
    }
};

Go

func lexicalOrder(n int) []int {
	var res []int
	var dfs func(int, int)
	dfs = func(i, n int) {
		if i > n {
			return
		}
		res = append(res, i)
		for j := 0; j < 10; j++ {
			dfs(i*10+j, n)
		}
	}

	for i := 1; i < 10; i++ {
		dfs(i, n)
	}
	return res
}

...