字典数排序
题目内容
给定一个整数 n, 返回从 1 到 n 的字典顺序。
例如，
给定 n =13，返回 [1,10,11,12,13,2,3,4,5,6,7,8,9] 。
请尽可能的优化算法的时间复杂度和空间复杂度。 输入的数据 n 小于等于 5,000,000。
解题过程
初次接触这题,我试图用快速排序,堆排序等排序方式去解决该问题，但是程序运行之后，要么内存不足,要么复杂度达不到时间要求。 经过两天的瞎折腾，我突然茅塞顿开，找到了以下规律。
如果 n<10,则 1 后面的数字为 2，否则 1 后面的数组为 10。
如果 n<20,则 2 后面的数字为 3，否则 1 后面的数组为 20。
如果 n<30,则 3 后面的数字为 4，否则 1 后面的数组为 30。
经总结如下
如果m<n
如果 m*10<=n
则下一位为m*10
否则下一位为m+1;
否则
结束。
代码示例
创建二叉树的类
/// <summary>
/// 二叉树
/// </summary>
public class TreeNode
{
public static int Globalvalue = 1;
public int value;
public TreeNode leftNode;
public TreeNode rightNode;
/// <summary>
/// 构造函数
/// </summary>
/// <param name="x"></param>
public TreeNode(int x)
{
value = x;
int leftvalue = x * 10;
int rightvalue = x + 1;
if (leftvalue <= Globalvalue)
{
leftNode = new TreeNode(leftvalue);
}
if (rightvalue <= Globalvalue && rightvalue % 10 != 0)
{
rightNode = new TreeNode(rightvalue);
}
}
}
二叉树的前序遍历
/// <summary>
/// 前序遍历
/// </summary>
/// <param name="tn"></param>
/// <param name="result"></param>
public void preOrder(TreeNode tn, List<int> result)
{
result.Add(tn.value);
if (tn.leftNode != null)
{
preOrder(tn.leftNode, result);
}
if (tn.rightNode != null)
{
preOrder(tn.rightNode, result);
}
}
调用前序排序方法。
/// <summary>
/// 执行排序
/// </summary>
/// <param name="n"></param>
/// <returns></returns>
public IList<int> LexicalOrder(int n)
{
TreeNode.Globalvalue = n;
TreeNode tn = new TreeNode(1);
List<int> result = new List<int>();
preOrder(tn, result);
return result;
}
总结
该方案并不是通过测试用例耗时最短的方法，毕竟不构造 TreeNode 类速度会更快，但是恰好复习了一下大学时候所学的二叉树遍历的相关知识,也是挺好的。