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 NAO机器人的录音程序保存问题
  • ¥15 C#读写EXCEL文件,不同编译
  • ¥15 MapReduce结果输出到HBase,一直连接不上MySQL
  • ¥15 扩散模型sd.webui使用时报错“Nonetype”
  • ¥15 stm32流水灯+呼吸灯+外部中断按键
  • ¥15 将二维数组,按照假设的规定,如0/1/0 == "4",把对应列位置写成一个字符并打印输出该字符
  • ¥15 NX MCD仿真与博途通讯不了啥情况
  • ¥15 win11家庭中文版安装docker遇到Hyper-V启用失败解决办法整理
  • ¥15 gradio的web端页面格式不对的问题
  • ¥15 求大家看看Nonce如何配置