Lexicographical Numbers

Desicription

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

Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
std::vector<int> lexicalOrder(int n) {
auto stringVector = std::vector<std::string>(n);
for(int i = 1; i <= n; i++) {
stringVector[i - 1] = std::to_string(i);
}

std::sort(stringVector.begin(), stringVector.end(), std::less<std::string>{});
auto intVector = std::vector<int>(n);
for(int i = 0; i < intVector.size(); i++) {
intVector[i] = std::stoi(stringVector[i]);
}

return intVector;
}
};