小埋社区

    • 登录
    • 版块
    • 最新
    • 标签
    • 热门
    • 用户
    • 群组

    假如有10万条数据,按某个类型为Integer的列降序排列,如何快速找出前100条数据

    编程
    数据库 算法
    3
    4
    269
    正在加载更多帖子
    • 从旧到新
    • 从新到旧
    • 最多赞同
    回复
    • 在新帖中回复
    登录后回复
    此主题已被删除。只有拥有主题管理权限的用户可以查看。
    • Bruce
      Bruce ACG 最后由 编辑

      可以理解为生成一个排行榜,只显示某项数据前100的人的ID和这项数据

      select id, score from datatable order by score desc limit 100;
      

      这样应该是只利用数据库的话,最快的方式,但是有没有可能,直接把结果查出来,不排序,然后交给优化算法去排序
      PS: 假设内存无限大

      1 条回复 最后回复 回复 引用 0
      • Bruce
        Bruce ACG 最后由 编辑

        感觉我也快变成轮子哥了

        1 条回复 最后回复 回复 引用 0
        • 闲淡酱
          闲淡酱 站长 最后由 编辑

          select top 100
          

          应该没错。。。关键词是top

          1 条回复 最后回复 回复 引用 0
          • a-wing
            a-wing 最后由 编辑

            如果把这个定义为算法题的多话。不应该考虑数据库

            换句话说就是从十万数据里取 top 100

            刚想到一直空间复杂度和时间复杂度都很低的办法

            1. 先取前 100 个数。对着 100 个数进行排序(排序算法随便选)。先把这个序列叫 top100
            2. 取 min(top100)。和剩余数比较:如果比 min(top100) 小,就忽略。如果比 min(top100) 大,那就把这个数插入排序到 top100 里。(这样min(top100)也会跟着更新。继续比较,直到完全遍历完。这时的 top100 里的数就是真正的 "top100"

            这样只遍历一遍就可以取出 top100

            1 条回复 最后回复 回复 引用 0
            • First post
              Last post
            © 2017-2023 小埋社区 All Rights Reserved | 皖ICP备17016228号-2