讨论/技术交流/十万个手机号码排序/
十万个手机号码排序

在面试时被问到的,有什么好的思路吗?

2
共 25 个回复

基数排序?

8

《编程珠玑》第二版 好像有一样的问题
书 第一章
1.PNG
可以下个电子版书参考下(只是提供个思路)

3

怎么个排序
是按号码段区分
还是数字高低?
头像好像我的渣男朋友何某人啊

3

你好,你说的有点问题。
基数排序是从低位到高位依次进行排序,麻烦再考证一下。谢谢!

2

十万个的话数量级也太小了,一般这种手机号排序的题目可以按位用桶排序,因为每个位就10种可能的值,所以用十个桶从低位往高位依次桶排,时间复杂度O(n*11)->O(n)。当然桶排可以换成其他稳定的排序算法,要求稳定是因为不能影响已经排过序的更高位的有序性。

2

前缀树或者tire树吧

2

~(≧▽≦)/~

1

这个应该桶排序最快吧

1

做个字典树(3)(4)(4)
深度为 3
然后每个栈都放一个list 放存所在的区间

class node{
String val;//00-99
List<node>list;//记得排序
}

取的话DFS 遍历就得到了

1

位图法吧

1