网页资讯视频图片知道文库贴吧地图采购
进入贴吧全吧搜索
java吧 关注：1,241,661贴子：12,712,683

字节面试一道topK没答出来，请教各位大佬

只看楼主收藏回复

有1T的int数据，内存肯定放不下，问如何得到这些数据里出现频率最高的100个数字？
IP属地:北京1楼2021-05-11 19:41回复
    经典分治，切成无数个小文件统计再逐步汇总
    IP属地:浙江2楼2021-05-11 19:45
    收起回复
      贴吧算法一般都很差
      IP属地:上海来自Android客户端3楼2021-05-11 21:23
      收起回复
        hash分治加最小堆
        来自Android客户端4楼2021-05-11 21:30
        收起回复
          这个问题，几年前我学数据结构算法时，几年前我的大佬同学就问过我。
          。。。。
          IP属地:日本5楼2021-05-11 22:05
          回复
            二叉堆最小堆
            来自iPhone客户端6楼2021-05-11 22:25
            回复
              可以去了解下数据库orderby咋实现的
              limit:堆选
              无limit:快排
              超过buffer:归并排
              然后你可以了解下分表分库的limit咋实现的
              或者有一道经典的25匹马找前三的问题
              基础题
              IP属地:浙江来自Android客户端8楼2021-05-12 09:43
              回复
                MappedByteBuffer文件内存映射，轻松搞定
                IP属地:江苏来自iPhone客户端9楼2021-05-12 10:22
                回复
                  最小堆
                  IP属地:北京来自Android客户端11楼2021-05-12 12:18
                  收起回复
                    算一下int类型所有数最多占用内存空间，是2的32次方也就是4g个数。这里映射成int数组就行了。如果太小了，比如用byte，计数的数范围可能不够用，然后在对应位置上存储计数，算上虚拟内存一般是够用的。
                    IP属地:广东来自Android客户端12楼2021-05-12 13:29
                    收起回复
                      读100个数据到内存，建堆，然后再读数据更新堆，时间复杂度o（nlog100）
                      IP属地:上海来自Android客户端14楼2021-05-12 14:25
                      收起回复
                        内存放不下，用文件存储统计过程次数。用文件做草稿，最后统计。
                        IP属地:山东来自Android客户端15楼2021-05-12 16:05
                        收起回复
                          看题目描述内存放不下，似乎是外部排序？
                          IP属地:上海来自Android客户端16楼2021-05-12 16:15
                          回复
                            丢进hdfs mapreduce
                            IP属地:浙江来自Android客户端17楼2021-05-12 16:17
                            回复
                              定一个int[Integer.MAX] list的数组不就行了吗 然后找到一个数字就是list[num]=list[num]+1，最后再排序，如果他的内存连一个数组都放不下的话那就不知道了
                              IP属地:广东来自Android客户端19楼2021-05-12 17:21
                              收起回复

                                扫二维码下载贴吧客户端

                                下载贴吧APP
                                看高清直播、视频！
                                发表回复
                                发贴请遵守贴吧协议及“七条底线”贴吧投诉
                                内  容:
                                  查看全部
                                发 表
                                保存至快速回贴

                                发布成功
                                去贴吧APP订阅抽奖结果通知
                                扫码进入贴吧APP
                                ···········
                                开奖后第一时间站内信通知
                                ···········
                                中奖结果全员公示