386 Lexicographical Numbers 字典序排数
Description:
Given an integer n, return 1 - n in lexicographical order.
Example:
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.
题目描述:
给定一个整数 n, 返回从 1 到 n 的字典顺序。
示例 :
给定 n = 13，返回 [1,10,11,12,13,2,3,4,5,6,7,8,9] 。
请尽可能的优化算法的时间复杂度和空间复杂度。 输入的数据 n 小于等于 5,000,000。
思路:
- 先排序字符串, 然后将排序好的字符串转换为整数
时间复杂度O(nlgn), 空间复杂度O(n) - 设置一个指针
比如需要放 1-130
指针开始指向 1, 下一个应该放 10, 所以比较指针 * 10和 n的大小关系
指针自乘 10直到超过 n
这时已经放入了 [1, 10, 100],
由于 100 * 10 > 130, 此时下一个应该是 11, 这时指针需要从 100移动到 11, 比较指针和 n的大小, 指针超过 n就自除 10, 然后自增直到 20, 下一个数为2, 所以当低位是 0的时候, 需要去掉
时间复杂度O(nlgn), 空间复杂度O(1)
代码:
C++:
class Solution
{
public:
vector<int> lexicalOrder(int n)
{
vector<int> result(n);
int cur = 1;
for (int i = 0; i < n; i++)
{
result[i] = cur;
if (cur * 10 <= n) cur *= 10;
else
{
if (cur >= n) cur /= 10;
++cur;
while (!(cur % 10)) cur /= 10;
}
}
return result;
}
};
Java:
class Solution {
public List<Integer> lexicalOrder(int n) {
String list[] = new String[n];
for (int i = 1; i < n + 1; i++) list[i - 1] = String.valueOf(i);
Arrays.sort(list);
List<Integer> result = new ArrayList<>(n);
for (String s : list) result.add(Integer.valueOf(s));
return result;
}
}
Python:
class Solution:
def lexicalOrder(self, n: int) -> List[int]:
return sorted(range(1, n + 1), key=str)
