字典数排序

题目内容

给定一个整数 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。

经总结如下

1
2
3
4
5
6
如果m<n
如果 m*10<=n
则下一位为m*10
否则下一位为m+1;
否则
结束。

代码示例

创建二叉树的类

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
/// <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);
}
}
}

二叉树的前序遍历

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
/// <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);
}
}

调用前序排序方法。

1
2
3
4
5
6
7
8
9
10
11
12
13
/// <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类速度会更快,但是恰好复习了一下大学时候所学的二叉树遍历的相关知识,也是挺好的。

参考资料

作者

stone liu

发布于

2018-05-01

更新于

2024-09-06

许可协议

评论