当前位置: 首页 > news >正文

算法通关村第十五关——从40亿个数中产生一个不存在的数的处理方法

1.从40个亿中产生一个不存在的整数

题目要求:给定一个输入文件,包含40亿个非负整数,请设计一个算法,产生一个不存在该文件中的整数,假设你有1GB的内存来完成这项任务。****

解题中心思想:存储的不是这40亿个数据本身,而是其对应的位置。

本题不用写代码,能把方法过程说清楚就可以。

1.1 位图存储大数据的原理

方法8 bit1B,一个32位整数需要4B的存储空间,40亿个数就是 40亿 * 4B,约为16GB,用位图来做的话会更节省空间,因为位图的每个位置只能用0或1进行状态表示,这样就只需要40亿 / 8 = 5亿字节,也就是大约500M的存储空间。

过程:具体来做就是先遍历这40亿个数,并把遍历的每个数在位图上的相对位置设置为1。这40亿个数遍历结束后,开始遍历位图,看看哪个位置上的状态为0,就说明这个位置对应的数没有在40亿个数中出现,位图遍历结束后就能得到所有未在40亿个数中出现过的数。

1.2 使用10MB来存储呢?

如果使用10MB来存储,位图也搞不定了,这个时候就得使用分块思想,用时间换空间,通过两次遍历来处理。

40亿个数需要约500MB的空间,如果只有10MB的空间,至少需要50个块才可以。一般划分块都使用2的幂次方的整数倍,此处划分为64个块是合理的。

首先将 0 − 2 32 0-2^{32} 0232 这个范围的数平均分成64个区间,每个区间是67 108 864个数,因为一共只有40亿个数,所以在统计每一个区间上的数有多少时,肯定会有至少一个区间上的计数小于67 108 864。利用这一点可以找出其中一个没出现过的数。具体过程如下:

第一次遍历:先申请长度位64的整型数组countArr[0, ..., 63]countArr[i]用来统计区间i上的数有多少。遍历40亿个数,跟去当前数是多少来决定哪一个区间上的计数增加。比如,如果当前数为2 567 278 1892 567 278 189 / 67 108 864 = 38 ,所以第38个区间上计数增加countArr[51]++。遍历完40亿个数之后,遍历countArr,必然会有某一个位置上的值(countArr[i])小于67 108 864,表示第i区间上至少有一个数没出现过。

此时使用的内存是非常小的,是countArr的大小(64 * 4B)

假设找到第37区间上的计数小于67 108 864,那么对这40亿个数据进行第二次遍历:

  1. 申请长度为67 108 864的位图(bit map),占用大约8MB的空间,记为bitArr[0, ... , 67108863]
  2. 遍历这40亿个数,此时的遍历只关注落在第37区间上的数,记为num(num满足 num / 67108864 = == 37),其他区间的数全部忽略。
  3. 如果步骤2的num在第37区间上,将bitArr[num - 67108864 * 37]的值设置为1,也就是只做第37区间上的数的bitArr映射。
  4. 遍历完40亿个数之后,在bitArr上必然存在没被设置成1的位置,假设第i个位置上的值没被设置成1,那么67108864 * 37 + i这个数就是一个没出现过的数

步骤小结:

  • 根据 10MB 的内存限制,确定统计区间的大小,就是第二次遍历时的 bitArr 大小。
  • 利用区间计数的方式,找到那个计数不足的区间,这个区间上肯定有没出现的数。
  • 对这个区间上的数做 bit map 映射,再遍历bit map,找到一个没出现的数即可。

1.3 如何确定分块的区间

上面的例子中,采用两次遍历,第一次将数据分成64块刚好解决问题,为什么不是128块,32块,16块或者其他块数呢?

这是主要为了保障第二次遍历时每个块都能放进这10MB的空间中。 2 23 < 10 M B < 2 24 2^{23} < 10MB < 2^{24} 223<10MB<224,而 2 23 = 8388608 2^{23} = 8388608 223=8388608 大约是8MB,也就是说我们一次的分块大小只能为8MB左右。我们在第二次遍历时分成64块刚好满足要求,这是最少得分成64块,当然如果分成128块、256块也是可以的。

相关文章:

算法通关村第十五关——从40亿个数中产生一个不存在的数的处理方法

1.从40个亿中产生一个不存在的整数 题目要求&#xff1a;给定一个输入文件&#xff0c;包含40亿个非负整数&#xff0c;请设计一个算法&#xff0c;产生一个不存在该文件中的整数&#xff0c;假设你有1GB的内存来完成这项任务。**** 解题中心思想&#xff1a;存储的不是这40亿…...

软件项目开发的流程及关键点

软件项目开发的流程及关键点 graph LR A[需求分析] --> B[系统设计] B --> C[编码开发] C --> D[测试验证] D --> E[部署上线] E --> F[运维支持]在项目开发的流程中&#xff0c;首先是进行需求分析&#xff0c;明确项目的目标和功能要求。接下来是系统设计&am…...

全球变暖问题(floodfill 处理联通块问题)

全球变暖问题 文章目录 全球变暖问题前言题目描述题目分析边界问题的考虑岛屿是否被淹没判断&#xff1a;如何寻找联通块&#xff1a; 代码预告 前言 之前我们介绍了 bfs算法在二维&#xff0c;三维地图中的应用&#xff0c;现在我们接续进行拓展&#xff0c;解锁floodfill 算…...

由于找不到vcruntime140_1.dll怎么修复,详细修复步骤分享

在使用电脑过程中&#xff0c;可能会遇到一些错误提示&#xff0c;其中之一是找不到vcruntime140_1.dll的问题。这使得许多用户感到困扰&#xff0c;不知道该如何解决这个问题。小编将详细介绍vcruntime140_1.dll的作用以及解决找不到该文件的方法&#xff0c;帮助你摆脱困境。…...

算法 三数之和-(双指针)

牛客网: BM54 题目: 数组中所有不重复的满足三数之和等于0的数&#xff0c;非递减形式。 思路: 数组不小于3。不重复非递减&#xff0c;需先排序。使用idx从0开始遍历到n-2, 如果出现num[idx]num[idx-1]的情况&#xff0c;忽略继续下一个idx&#xff1b;令left idx1, right …...

AB实验总结

互联网有线上系统&#xff0c;可做严格的AB实验。传统行业很多是不能做AB实验的。 匹配侧是采用严格的AB实验来进行模型迭代&#xff0c;而精细化定价是不能通过AB实验来评估模型好坏&#xff0c;经历过合成控制法、双重差分法&#xff0c;目前采用双重差分法来进行效果评估。…...

sklearn包中对于分类问题,如何计算accuracy和roc_auc_score?

1. 基础条件 import numpy as np from sklearn import metricsy_true np.array([1, 7, 4, 6, 3]) y_prediction np.array([3, 7, 4, 6, 3])2. accuracy_score计算 acc metrics.accuracy_score(y_true, y_prediction)这个没问题 3. roc_auc_score计算 The binary and mul…...

python温度转换程序

1.使用pycharm运行温度转换程序&#xff0c;尝试将温度单位设在前面 2.参照温度转换程序,自己写一个关于货币转换、长度转换、重量转换或者面积转换的程序 循环函数 def convertemperature():temperature ""while (temperature ! "q"):temperature in…...

Vue2中10种组件通信方式和实践技巧

目录 1&#xff0c;props / $emit1.1&#xff0c;一个需求方法1方法2 1.2&#xff0c;v-model 和 .syncv-model.sync 2&#xff0c;$children / $parent3&#xff0c;ref4&#xff0c;$attrs / $listeners$attrs$listenersinheritAttrs1.1 的问题的第3种解决方法 5&#xff0c;…...

Flutter flutter.minSdkVersion的实际文件位置

Flutter 项目的Android相关版本号配置&#xff1a; flutter.minSdkVersion 的版本号配置文件实际路径&#xff1a; …/flutter_sdk/packages/flutter_tools/gradle/src/main/groovy/flutter.groovy Flutter版本号如下&#xff1a; bzbMacBook-Pro ccsmec % flutter --version …...

python生成PDF报告

前言 最近接到了一个需求-将项目下的样本信息汇总并以PDF的形式展示出来&#xff0c;第一次接到这种PDF的操作的功能&#xff0c;还是有点慌的&#xff0c;还好找到了reportlab这个包&#xff0c;可以定制化向PDF写内容&#xff01; 让我们由简入深进行讲解 一、reportlab是…...

在visual studio里安装Python并创建python工程

在2009年&#xff0c;云计算开始发力&#xff0c;Python、R、Go这些天然处理批量计算的语言也迅猛发展。微软在2010年&#xff0c;把Python当成一个语言包插件&#xff0c;集成到了visual studio 2010里。在"云优先&#xff0c;移动优先"的战略下&#xff0c;于2015年…...

AIGC(生成式AI)试用 6 -- 从简单到复杂

从简单到复杂&#xff0c;这样的一个用例该如何设计&#xff1f; 之前浅尝试用&#xff0c;每次尝试也都是由浅至深、由简单到复杂。 一点点的“喂”给生成式AI主题&#xff0c;以测试和验证生成式AI的反馈。 AIGC&#xff08;生成式AI&#xff09;试用 1 -- 基本文本_Role…...

竞赛 基于深度学习的人脸识别系统

前言 &#x1f525; 优质竞赛项目系列&#xff0c;今天要分享的是 基于深度学习的人脸识别系统 该项目较为新颖&#xff0c;适合作为竞赛课题方向&#xff0c;学长非常推荐&#xff01; &#x1f9ff; 更多资料, 项目分享&#xff1a; https://gitee.com/dancheng-senior/…...

uniapp:APP开发,后台保活

前言&#xff1a; 在ios中&#xff0c;软件切换至后台、手机息屏&#xff0c;过了十来秒软件就会被系统挂起&#xff0c;APP内的任务就不能继续执行&#xff1b;在android中&#xff0c;默认情况下&#xff0c;软件在后台运行的时候&#xff0c;触发某些特定条件的情况下&…...

vue2 项目中嵌入视频

案例&#xff1a; 代码&#xff1a; <template><div class"schematicDiagramIndex"><el-container><el-aside width"20rem"> <!-- <h4 style"font-size: 18px">视频演示</h4>--><div styl…...

第二章 进程与线程 十二、进程同步与进程互斥

目录 一、进程同步 1、定义 二、进程互斥 1、定义 2、四个部分 3、原则 一、进程同步 1、定义 进程同步是指在多个进程之间协调执行顺序的一种机制&#xff0c;使得进程按照一定的顺序执行&#xff0c;以避免出现不一致的情况。常见的实现方式有信号量、管程、屏障等。…...

Linux内核链表(list)移植到任意平台

一、前言 linux内核链表在include/linux/list.h文件中&#xff0c;内核中实现的链表比较简洁&#xff0c;实用性很强&#xff0c;因此想把它单独移植出来使用。 内核中的代码只能使用gnuc编译器编译&#xff0c;stdc编译器编译是会报错的&#xff0c;主要是因为typeof这个宏是…...

【操作系统】聊聊什么是CPU上下文切换

对于linux来说&#xff0c;本身就是一个多任务运行的操作系统&#xff0c;运行远大于CPU核心数的程序&#xff0c;从用户视角来看是并发执行&#xff0c;而在CPU视角看其实是将不同的CPU时间片进行分割&#xff0c;每个程序执行一下&#xff0c;就切换到别的程序执行。那么这个…...

CMake教程-第 2 步 添加一个库

CMake教程-第 2 步 添加一个库 1 CMake教程介绍2 学习步骤Step 1: A Basic Starting PointStep 2: Adding a LibraryStep 3: Adding Usage Requirements for a LibraryStep 4: Adding Generator ExpressionsStep 5: Installing and TestingStep 6: Adding Support for a Testin…...

vscode(仍待补充)

写于2025 6.9 主包将加入vscode这个更权威的圈子 vscode的基本使用 侧边栏 vscode还能连接ssh&#xff1f; debug时使用的launch文件 1.task.json {"tasks": [{"type": "cppbuild","label": "C/C: gcc.exe 生成活动文件"…...

ardupilot 开发环境eclipse 中import 缺少C++

目录 文章目录 目录摘要1.修复过程摘要 本节主要解决ardupilot 开发环境eclipse 中import 缺少C++,无法导入ardupilot代码,会引起查看不方便的问题。如下图所示 1.修复过程 0.安装ubuntu 软件中自带的eclipse 1.打开eclipse—Help—install new software 2.在 Work with中…...

在QWebEngineView上实现鼠标、触摸等事件捕获的解决方案

这个问题我看其他博主也写了&#xff0c;要么要会员、要么写的乱七八糟。这里我整理一下&#xff0c;把问题说清楚并且给出代码&#xff0c;拿去用就行&#xff0c;照着葫芦画瓢。 问题 在继承QWebEngineView后&#xff0c;重写mousePressEvent或event函数无法捕获鼠标按下事…...

【p2p、分布式,区块链笔记 MESH】Bluetooth蓝牙通信 BLE Mesh协议的拓扑结构 定向转发机制

目录 节点的功能承载层&#xff08;GATT/Adv&#xff09;局限性&#xff1a; 拓扑关系定向转发机制定向转发意义 CG 节点的功能 节点的功能由节点支持的特性和功能决定。所有节点都能够发送和接收网格消息。节点还可以选择支持一个或多个附加功能&#xff0c;如 Configuration …...

es6+和css3新增的特性有哪些

一&#xff1a;ECMAScript 新特性&#xff08;ES6&#xff09; ES6 (2015) - 革命性更新 1&#xff0c;记住的方法&#xff0c;从一个方法里面用到了哪些技术 1&#xff0c;let /const块级作用域声明2&#xff0c;**默认参数**&#xff1a;函数参数可以设置默认值。3&#x…...

Java详解LeetCode 热题 100(26):LeetCode 142. 环形链表 II(Linked List Cycle II)详解

文章目录 1. 题目描述1.1 链表节点定义 2. 理解题目2.1 问题可视化2.2 核心挑战 3. 解法一&#xff1a;HashSet 标记访问法3.1 算法思路3.2 Java代码实现3.3 详细执行过程演示3.4 执行结果示例3.5 复杂度分析3.6 优缺点分析 4. 解法二&#xff1a;Floyd 快慢指针法&#xff08;…...

ThreadLocal 源码

ThreadLocal 源码 此类提供线程局部变量。这些变量不同于它们的普通对应物&#xff0c;因为每个访问一个线程局部变量的线程&#xff08;通过其 get 或 set 方法&#xff09;都有自己独立初始化的变量副本。ThreadLocal 实例通常是类中的私有静态字段&#xff0c;这些类希望将…...

高抗扰度汽车光耦合器的特性

晶台光电推出的125℃光耦合器系列产品&#xff08;包括KL357NU、KL3H7U和KL817U&#xff09;&#xff0c;专为高温环境下的汽车应用设计&#xff0c;具备以下核心优势和技术特点&#xff1a; 一、技术特性分析 高温稳定性 采用先进的LED技术和优化的IC设计&#xff0c;确保在…...

shell脚本质数判断

shell脚本质数判断 shell输入一个正整数,判断是否为质数(素数&#xff09;shell求1-100内的质数shell求给定数组输出其中的质数 shell输入一个正整数,判断是否为质数(素数&#xff09; 思路&#xff1a; 1:1 2:1 2 3:1 2 3 4:1 2 3 4 5:1 2 3 4 5-------> 3:2 4:2 3 5:2 3…...

Yii2项目自动向GitLab上报Bug

Yii2 项目自动上报Bug 原理 yii2在程序报错时, 会执行指定action, 通过重写ErrorAction, 实现Bug自动提交至GitLab的issue 步骤 配置SiteController中的actions方法 public function actions(){return [error > [class > app\helpers\web\ErrorAction,],];}重写Error…...