while1_! 2023-04-03 00:00 采纳率: 100%
浏览 10
已结题

如何使用数据结构与算法优雅地实现边统计边排序?

我感觉对于关键字的统计和排序很多情况都是基于已经知道所有关键字的情况下进行哈希表统计然后排序。
但是假如我并不能事先知道有哪些关键字我只能一次一次得像开盲盒一样去获取关键字,并且每一次获取后我都要更新排序结果。
我想过如果用数组,每次获取关键词后查找倒是可以用二分查找实现O(logn),当然也可以添加一个哈希表实现近似O(1)实现查找。如果关键字存在还好,顶多就是交换关键字位置,要是不存在就要进行新增元素并且移动了。
然后我就想用链表,每次获取一个关键字要么就是在链表头部增一个节点,要么就是把原来存在的关键字节点移动到出现次数加一的位置,至少新增或者移动复杂度是相较于数组是降低了。但是要找到存在的关键字节点的复杂度变成了O(n)。我觉得还是可以使用哈希表存储关键字和节点地址或者引用实现O(1)查找。
我还想到了个方案,用红黑树,但是红黑树我没听说过有更新操作,但可以用删除和新增两个操作来代替,但是感觉十分不优雅。
我想问到底最优雅的方法是啥?是不是本身就存在一个我还不了解的方案解决这个问题。

  • 写回答

2条回答 默认 最新

  • threenewbee 2023-04-03 00:35
    关注

    堆排序吧,或者二叉排序树,也就是你说的红黑树

    本回答被题主选为最佳回答 , 对您是否有帮助呢?
    评论
查看更多回答(1条)

报告相同问题?

问题事件

  • 系统已结题 4月20日
  • 已采纳回答 4月12日
  • 创建了问题 4月3日

悬赏问题

  • ¥15 flutter 编译web端出错,如何解决?
  • ¥20 使用AT89C51微控制器和MAX7219驱动器来实现0到99秒的秒表计数,有开始和暂停以及复位功能,请写出C语言程序
  • ¥15 51单片机 双路ad同步采样
  • ¥15 使用xdocreport 生成word
  • ¥15 请教怎么用MATLAB求坐标
  • ¥15 gradle整合es,在创建索引时报错
  • ¥15 关于模型训练的一个问题
  • ¥15 装了几千台服务器从来没遇到这种问题,哎看下哪位帮我解决吧
  • ¥15 单片机程序上的困难问题
  • ¥15 请教某软件缓存Ts文件破解合并mp4的方法