60分加油站

题目内容

给定一个整数 n, 返回从 1 到 n 的字典顺序。

例如，

给定 n =1 3，返回 [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类速度会更快，但是恰好复习了一下大学时候所学的二叉树遍历的相关知识,也是挺好的。

参考资料

• 字典序排数解题过程
• 386. 字典序排数