思考题: 找到出现次数最多的数

2023-12-01 11:48
文章标签 次数 找到 最多 思考题

本文主要是介绍思考题: 找到出现次数最多的数,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

题目说明

有一个包含20亿个全是32位整数的大文件,在其中找到出现次数最多的数。

题目要求

内存限制为2GB。

 

实现思路

想要在很多整数中找到出现次数最多的数,通常的做法是使用哈希表对出现的每

一个数做词频统计,哈希表的key是某一个整数,value是这个数出现的次数。就本题来说,一共有20亿个数,哪怕只是一个数出现了20亿次,用32位的整数也可以表示其出现的次数而不会产生溢出,所以哈希表的key需要占用4B,value也是4B。那么哈希表的一条记录(key,value)需要占用8B。最极端的情况是20亿个数都不同,那么在哈希表中可能需要产生20亿条记录,大约为16GB内存。这样内存会不够用,所以一次性用哈希表统计20亿个数的办法是有很大风险的。

解决办法是把包含20亿个数的大文件用哈希函数分成很多个小文件,根据哈希函数的性质,同一种数不可能被哈希到不同的小文件上。

假设哈希函数设计的足够好,可以将数字近乎平均的散列到每个小文件上。假设散列到8个小文件上,理论上每个文件占用的内存正好是2GB。当然为了更稳妥起见,我们可以分成更多的小文件,比如16个,20个,40个甚至更多。假设我们这里选择散列到16个小文件上。

接下来,我们计算得到16个小文件中各自出现次数最多的数,还有各自的次数统计。接下来只要选出这16个小文件各自的第一名中谁出现的次数最多即可。

                                          

这篇关于思考题: 找到出现次数最多的数的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/441044

相关文章

PTA求一批整数中出现最多的个位数字

作者 徐镜春 单位 浙江大学 给定一批整数,分析每个整数的每一位数字,求出现次数最多的个位数字。例如给定3个整数1234、2345、3456,其中出现最多次数的数字是3和4,均出现了3次。 输入格式: 输入在第1行中给出正整数N(≤1000),在第二行中给出N个不超过整型范围的非负整数,数字间以空格分隔。 输出格式: 在一行中按格式“M: n1 n2 ...”输出,其中M是最大次数,n

hdu 3065 AC自动机 匹配串编号以及出现次数

题意: 仍旧是天朝语题。 Input 第一行,一个整数N(1<=N<=1000),表示病毒特征码的个数。 接下来N行,每行表示一个病毒特征码,特征码字符串长度在1—50之间,并且只包含“英文大写字符”。任意两个病毒特征码,不会完全相同。 在这之后一行,表示“万恶之源”网站源码,源码字符串长度在2000000之内。字符串中字符都是ASCII码可见字符(不包括回车)。

在二叉树中找到两个节点的最近公共祖先(基于Java)

如题  题解 public int lowestCommonAncestor(TreeNode root, int o1, int o2) {//记录遍历到的每个节点的父节点。Map<Integer, Integer> parent = new HashMap<>();Queue<TreeNode> queue = new LinkedList<>();parent.put(roo

C语言练习题之 数组中出现次数超过一半的数

题目描述 给一个长度为 n 的数组,数组中有一个数字出现的次数超过数组长度的一半,请找出这个数字。 例如输入一个长度为9的数组[1,2,3,2,2,2,5,4,2]。由于数字2在数组中出现了5次,超过数组长度的一半,因此输出2。 数据范围:n≤50000,数组中元素的值0≤val≤10000 要求:空间复杂度:O(1),时间复杂度O(n) 输入描述: 保证数组输入非空,且保证有

【每日一题】LeetCode 2379.得到K个黑块的最少涂色次数(字符串、滑动窗口)

【每日一题】LeetCode 2379.得到K个黑块的最少涂色次数(字符串、滑动窗口) 题目描述 给定一个字符串 blocks,其中每个字符代表一个颜色块,可以是 ‘W’(白色)或 ‘B’(黑色)。你需要找到一个至少包含 k 个连续黑色块的子串。每次操作可以将一个白色块变成黑色块。你的任务是找到至少出现一次连续 k 个黑色块的最少操作次数。 和该题目类似:【每日一题】LeetCode 202

43. 1 ~ n 整数中 1 出现的次数【难】

comments: true difficulty: 中等 edit_url: https://github.com/doocs/leetcode/edit/main/lcof/%E9%9D%A2%E8%AF%95%E9%A2%9843.%201%EF%BD%9En%E6%95%B4%E6%95%B0%E4%B8%AD1%E5%87%BA%E7%8E%B0%E7%9A%84%E6%AC%A1%

0to1使用Redis实现“登录验证”次数限制

1 引言 系统为了避免密码遭到暴力破解,通常情况下需要在登录时,限制用户验证账号密码的次数,当达到一定的验证次数后,在一段时间内锁定该账号,不再验证。本章将用几行代码实现该功能,完整代码链接在文章最后。 2 原理介绍 可以看到在登录接口中,4行代码即可实现该功能,这里使用Redis可以很方便的记录“登录失败次数”,以及设置其失效时间(即锁定时间),主要步骤是: 账号登录时,当前账号“登录失

Spring是如何找到URL请求对应的Controller的

文章来源 原文作者:Spring MVC 原文地址: https://blog.csdn.net/hl233211/article/details/77450697 http://ddrv.cn/a/58528 本文转自网络文章,转载此文章仅为分享知识,如有侵权,请联系博主进行删除。 序:先贴一张SpringMVC整体的框架原理图 此文主要描述Spring在响应请求的时候是如何根据U

LeetCode438. 找到字符串中所有字母异位词(2024秋季每日一题 11)

给定两个字符串 s 和 p,找到 s 中所有 p 的 异位词 的子串,返回这些子串的起始索引。不考虑答案输出的顺序。 异位词 指由相同字母重排列形成的字符串(包括相同的字符串)。 示例 1: 输入: s = “cbaebabacd”, p = “abc” 输出: [0,6] 解释: 起始索引等于 0 的子串是 “cba”, 它是 “abc” 的异位词。 起始索引等于 6 的子串是

涨幅超过了90%,心动网络股价成V字后,TapTap找到流量源了吗?

心动公司发布了截至2024年6月30日止六个月的中期业绩。 在2024年上半年(24H1),公司实现总营收22.21亿元,较去年同期增长了26.7%。归属于母公司的净利润达到2.05亿元,同比激增127.4%。经调整后,归属于母公司的净利润更是攀升至2.37亿元,同比增长率高达110.0%。 与业绩对应的是股价变化。 自2024年初以来,在港股市场近30只游戏软件相关股票