第73天。
今天的题目是Lexicographical Numbers:
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.
emmm,lexicographical
是字典序的意思。
首先,这种有规律的题目一般用递归来写会比较简单(但是可能会超时),我们先找出它的规律,在不到n
的时候,没加入一个数字i,我们就要看i*10 ~ i*10 + 9
是否小于n
,如果小于我们就把它加入,然后在递归的进行判断。
有一点需要注意的就是,它是从1
开始的,所以我们一开始就要尝试的把1 ~ 9
加入,而不是0 ~ 9
:
1vector<int> lexicalOrder(int n) {2 vector<int> ret;3 //lexicalOrder(ret,n,1);4 for(int i = 1;i < 10 && i <= n;i++) {5 ret.push_back(i);6 lexicalOrder(ret,n,i*10);7 }8 return ret;9}10void lexicalOrder(vector<int> &vec,int n,int base) {11 for(int i = 0;i < 10;i++,base++) {12 if (base > n){ return; }13 vec.push_back(base);14 lexicalOrder(vec,n,10*base);15 }1 collapsed line
16}
然后是在dicuss
中看到的迭代解法:
1vector<int> lexicalOrder(int n) {2 vector<int> res(n);3 int cur = 1;4 for (int i = 0; i < n; i++) {5 res[i] = cur;6 if (cur * 10 <= n) {7 cur *= 10;8 } else {9 if (cur >= n)10 cur /= 10;11 cur += 1;12 while (cur % 10 == 0)13 cur /= 10;14 }15 }2 collapsed lines
16 return res;17}