[leetcode]386. Lexicographical Numbers

本文主要是介绍[leetcode]386. 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的整数，乍一看比较像字符串排序问题，要不要把数字转换为字符串并逐个排序呢？显然，对于这种大范围数字问题且排序问题，这是不划算的，开销太大。
自己动手写一写数字排列的要求会发现明显的规律，当允许继续往数字后面加0时，肯定先加0，不能加0后再开始最低位1到9增加，但增加到9之后就要回到高一位的讨论了。所以其实任意一个数字，在这个排序要求下，判断他的下一位应该是什么，即可看，能乘10就乘10，不能就让最低位在9以内增加。然后回到高一位继续。
基于这种朴素的思想，我们给出如下三种解法：

方法一：递归

vector<int> lexicalOrder(int n) {vector<int> res;helper(res, 1, n);return res;
}
void helper(vector<int>& res, int a, int n) {if (a <= n) {res.push_back(a);helper(res, a*10, n);if (a % 10 < 9) helper(res, ++a, n);else return;}else return;
}

方法二：栈，迭代

递归在内部也是使用了自己的栈来进行的，类似于二叉树遍历的问题，我们同样可以在这里自己用栈来迭代实现递归的效果，话说这个字典排序输出很像二叉树的先序遍历，大家自己体会。

vector<int> lexicalOrder(int n) {vector<int> res;stack<int> s;s.push(1);while (!s.empty()) {int cur = s.top();s.pop();res.push_back(cur);if (cur % 10 < 9 && cur + 1 <= n) s.push(cur + 1);if (cur * 10 <= n) s.push(cur * 10);}return res;
}

方法三：不使用额外空间解法

这里也可以很巧妙的利用十进制除法，在完成低位1到9的输出后直接除以10回到高一位，这种方法相比于前两种效率最高，但最难想到。

vector<int> lexicalOrder(int n) {vector<int> res(n, 0);int cur = 1;for (int i = 0; i < n; i++) {res[i] = cur;if (cur * 10 <= n) {cur = cur * 10;}else {if (cur >= n) cur = cur / 10;cur++;while (cur % 10 == 0) cur = cur / 10;//注意这里得是while不能只是if，因为199加1到200，我们需要回到2，while保证我们回到变化那一位}}return res;
}