LeetCode 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.
要求把1~n的n个数以字典序的方式输出。 明显不能先把int转换为string然后sort，这样肯定会超时。讨论区有一个大神的解法很厉害，学习一下，他通过枚举的方法一次性把1~n的字典序数组生成了。 假设我们枚举到当前数是cur，则下一个字典序的数是哪个呢。首先，下一个最小字典序的数肯定是末尾加0的，即cur*10。如果cur*10超过范围，则下一个最小字典序的数肯定是个数为加1，即cur+1。如果cur+1也超过范围了，则下一个最小字典序的数应该是十位数加1，个位数变为0，并且把个位删掉，即cur=cur/10+1。 代码如下： [cpp] class Solution { public: vector<int> lexicalOrder(int n) { vector<int> ans; int cur = 1; for (int i = 1; i <= n; ++i) { ans.push_back(cur); if (cur * 10 <= n)cur *= 10; else if (cur % 10 != 9 && cur + 1 <= n)++cur; else { while ((cur / 10) % 10 == 9)cur /= 10; cur = cur / 10 + 1; } } return ans; } }; [/cpp] 本代码提交AC，用时168MS。 举个例子，假设cur=45，则下一个数首先是450；如果450超过n，则下一个数应该是46；如果46也超过范围，则下一个数应该是5。如果遇到cur=499，且跳到了第2个if，++cur==500，但是明显下一个数应该是5，所以不能进入第2个if，进入到第3个if，不断把末尾的9去掉，然后高位加1变为5。]]>