TopK高频重复算法题

痛定思痛。 2022-09-08 00:05 294阅读 0赞

### 文章目录 ###

*  前言
 *  解法
 *  代码

# 前言 #

最近广州某大厂面，笔试也有算法，惊了~  
题目就是找出2G数据里头，重复最多的前100个，虚拟机只有1G内存

# 解法 #

1.首先是分治法  
因为内存不够，就1G1G来算咯，然后再将结果进行合并即可。

2.就是一个TopK 的问题，可以采用堆

3.重复次数最多  
需要用map来记录key对应出现的次数有多少

# 代码 #

public static void main(String[] args) { 
            /*PriorityQueue<Integer> queue = new PriorityQueue(); queue.add(2); queue.add(1); queue.add(3); queue.add(2); while (queue.size()!=0){ System.out.println(queue.poll()); }*/
    
            Comparator<Key> comparator = (o1, o2) -> o2.value-o1.value;
            PriorityQueue<Key> queue1 = new PriorityQueue<>(comparator);
            Map<String,Integer> map = new HashMap<>();
            List<String> list = new ArrayList<>();
            list.add("a");
            list.add("b");
            list.add("a");
            while (list.size()!=0){ 
                String value = list.remove(0);
                Integer mValue = map.get(value);
                if(null == mValue){ 
                    map.put(value,1);
                }else { 
                    map.put(value,mValue+1);
                }
            }
            for(Map.Entry<String,Integer> entry:map.entrySet()){ 
                System.out.println(entry.getKey()+" "+entry.getValue());
                queue1.add(new Key(entry.getKey(),entry.getValue()));
            }
            System.out.println(queue1.poll());
        }
        @Data
        static
        class Key{ 
            private String name;
            private Integer value;
    
            public Key(String name, Integer value) { 
                this.name = name;
                this.value = value;
            }
        }

发表评论取消回复

表情：

评论列表（有 0 条评论，294人围观）

还没有评论，来说两句吧...

相关阅读

相关高频面试题|RabbitMQ如何防止消息的重复消费？

一. 前言最近有很多小伙伴开始找工作，在面试时，面试官经常会问我们这样一个题目： RabbitMQ如何防止重复消费? 有很多小伙伴这个时候都在想，消息怎么还会重复消

港控/mmm°/ 2024年03月26日 14:44/ 0 赞/ 159 阅读

相关每天高频算法题-DAY3

题目一在一个 n \ m 的二维数组中，每一行都按照从左到右非递减的顺序排序，每一列都按照从上到下非递减的顺序排序。请完成一个高效的函数，输入这样的一个二维数组

逃离我推掉我的手/ 2023年10月13日 16:29/ 0 赞/ 145 阅读

相关 26. 删除排序数组中的重复项（高频题）

26. 删除排序数组中的重复项题目解题思路代码题目给定一个排序数组，你需要在原地删除重复出现的元素，使得每个元素只出现一次，返回移

一时失言乱红尘/ 2023年10月05日 20:32/ 0 赞/ 15 阅读

相关 js高频面试题（高频）

题目 1. js基本数据类型 2. 闭包是什么，写一个简单的闭包 3. 原型和原型链 4. 作用域 5. this 6. call、apply和bind 7.

喜欢ヅ旅行/ 2023年01月10日 14:33/ 0 赞/ 404 阅读

相关算法题：存在重复元素

算法题：存在重复元素题目描述示例 python代码执行效率题目描述给定一个整数数组，判断是否存在重复元素。如果任意一值在数

一时失言乱红尘/ 2022年12月27日 15:26/ 0 赞/ 227 阅读

相关算法 topK

> 给定一个无序数组，以及一个整数k，要求返回无序数组中的第k大的数字解法1：最大堆法（优先队列） 1. 原理：利用最大堆的特点，在将无序数组构建成最大堆后，执行k

痛定思痛。/ 2022年12月21日 03:20/ 0 赞/ 299 阅读

相关大厂高频手撕算法题

> 目前互联网行业目前正在处于内卷状态，各个大厂不断提高招人门槛，前端工程师找工作也越发艰难，为了助力各位老铁能够在面试过程中脱颖而出，我结合自己的面试经验，准备了这三十六道面

客官°小女子只卖身不卖艺/ 2022年12月11日 06:28/ 0 赞/ 298 阅读

相关 topk算法

从一亿个数中，取出前100个最大数。最小堆排序。 1.首先读入前100个数，排成最小堆，时间复杂度为O（klogk）（k为数组的大小即为100）。 2.然后遍历后续

阳光穿透心脏的1/2处/ 2022年11月25日 00:50/ 0 赞/ 237 阅读

相关 TopK高频重复算法题

文章目录前言解法代码前言最近广州某大厂面，笔试也有算法，惊了~ 题目就是找出2G数据里头，重复最多的前100个，虚拟机只有1G内存

痛定思痛。/ 2022年09月08日 00:05/ 0 赞/ 295 阅读

相关 TopK算法排序

本文转自:[http://blog.csdn.net/Together\_CZ/article/details/65945838?locationNum=15&fps=1][h

电玩女神/ 2022年05月31日 11:19/ 0 赞/ 331 阅读