somebody0101 2015-06-14 05:34 采纳率: 0%
浏览 1998

一道面试题(关于千万量级数据结构排序)

题目:
已知文件中存有全国英语六级历年来的成绩(千万级别,考生分数都是正整数,最高710分),每一行都是一个人的姓名、考号和成绩,请你对考生的成绩从高到低进行排序,输出到另一个文件中。
格式 如下:
李四,201008823,678;
张三,201007432,356;
王五,201322233,464;
排序后:
李四,201008823,678;
王五,201322233,464;
王五,201322233,464;
要求:使空间复杂度和时间复杂度尽可能低,希望可以达到时间复杂度为O(n)。按目前数据量预计计算机内存足够。可以用伪代码或说明思路
刚注册,没有分可悬赏,但应该是个不错的题。。

    以下是我的思路,但是不能完全解答出来,请高手提提建议:
    1.首先这个排序的依据是分数,而英语四级考试分数有范围0-710分。题目希望时间复杂度尽可能低。排除依据比较的排序算法如快速排序、选择排序,应该选择线性排序算法。
    2.再因为是千万级的数据,可以考虑使用桶排序,建立一个有711大小的桶(数组),遍历整个文档,根据分数大小在相应的桶号上计数。
    3.根据上面两步,基本是可以实现单纯的成绩排序。而且时间复杂度为O(n),空间复杂度也就是多一个桶数组。
    4.困难:问题是,基于计数的桶排序的对象如果是纯数字,好说。但是题目是带有姓名、考号和成绩三个属性的对象。怎么利用桶排序呢?

    谢谢!
  • 写回答

5条回答 默认 最新

  • CodeofWorker 2015-06-14 06:16
    关注

    其实这道题是单希望使用单循环即O(n),这个关键字在于分数,其实就是按分数做个最优的排序,是否不用想得太深呢?
    只要想的是怎么实现单循环排序。

    评论

报告相同问题?

悬赏问题

  • ¥15 请教:如何用postman调用本地虚拟机区块链接上的合约?
  • ¥15 为什么使用javacv转封装rtsp为rtmp时出现如下问题:[h264 @ 000000004faf7500]no frame?
  • ¥15 乘性高斯噪声在深度学习网络中的应用
  • ¥15 运筹学排序问题中的在线排序
  • ¥15 关于docker部署flink集成hadoop的yarn,请教个问题 flink启动yarn-session.sh连不上hadoop,这个整了好几天一直不行,求帮忙看一下怎么解决
  • ¥15 深度学习根据CNN网络模型,搭建BP模型并训练MNIST数据集
  • ¥15 C++ 头文件/宏冲突问题解决
  • ¥15 用comsol模拟大气湍流通过底部加热(温度不同)的腔体
  • ¥50 安卓adb backup备份子用户应用数据失败
  • ¥20 有人能用聚类分析帮我分析一下文本内容嘛