LeetCode Lexicographical Numbers

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。]]>

Leave a Reply

Your email address will not be published. Required fields are marked *