算法通关村15关 | 超大规模数据场景常见问题
1.用4KB内存寻找重复元素
题目:给定一个数组,包含从1到N的整数,N最大为32000,数组可能还有重复值,且N的取值不定,若只有4KB的内存可用,该如何打印数组中所有重复元素。
分析:
本身是一道海量数据问题的热身题,如果去掉“只有4KB”的要求,我们可以先创建一个大小为N的数组,然后将这些数据放进来,但是这里数组最大为32KB,而题目有4KB的内存限制,我们就必须先确定该如何存放这个数组。
如果只有4KB的空间,那么只能寻址`8*4*2^10`个比特,这个值比32000要大的,因此我们可以创建32000比特的位向量(比特数组),其中一个比特位置就代表一个整数。
利用这个位向量,就可以遍历访问整个数组。如果发现数组元素是v,那么就将位置为v的设置为1,碰到重复元素,就输出一下。
创建一个长度为32000的数组,每个位置存储0或者1,因为要存的最大值可能是32000,所以我们可以要存多大的数,就在对应的位置0换成1即可,比如存1,数组第1位就是1,索引是0,其余位置是0。存100数组第100位就是1,索引是99,其余位置是0。存10000数组第9999位是1,其余位置是0。如果在存某个数的时候发现这个位置是1,那么这值就重复,将这个值输出。
int是32位,占空间4B,1B=8bit,所以4kb空间就有超过4000*8个bit,所以数组长度是32000>>5,每个位置可以代表32个bit位,
代码示例
public void checkDuplicates(int[] array) {BitSet bs = new BitSet(320000);for (int i = 0; i < array.length; i++) {int num = array[i];int num0 = num - 1;if (bs.get(num0)) {System.out.println(num);} else {bs.set(num0);}}}class BitSet {int[] bitset;public BitSet(int size) {this.bitset = new int[size >> 5];}boolean get(int pos) {int wordNumber = (pos >> 5);//除以32int bitNumber = (pos & 0x1F);//取余32return (bitset[wordNumber] & (1 << bitNumber)) != 0;}void set(int pos) {int wordNumber = (pos >> 5);//除以32int bitNumber = (pos & 0x1F);//取余32bitset[wordNumber] |= 1 << bitNumber;}}
相关文章:
算法通关村15关 | 超大规模数据场景常见问题
1.用4KB内存寻找重复元素 题目:给定一个数组,包含从1到N的整数,N最大为32000,数组可能还有重复值,且N的取值不定,若只有4KB的内存可用,该如何打印数组中所有重复元素。 分析: 本身是…...
qemu编译与使用
文章目录 1、安装依赖2、下载qemu源码3、编译4、运行5、qemu参数 qemu 是一个硬件虚拟化程序(hypervisor that performs hardware virtualization),与传统的 VMware / VirtualBox 之类的虚拟机不同,它可以通过 binary translation…...

bazel远程构建(Remote Execution)
原理 既然 ActionResult 可以被不同的 Bazel 任务共享,说明 ActionResult 和 Action 在哪里执行并没有关系。因此,Bazel 在构建时,可以把 Action 发送给另一台服务器执行,对方执行完,向 CAS 上传 ActionResult&#x…...

uniapp 微信小程序仿抖音评论区功能,支持展开收起
最近需要写一个评论区功能,所以打算仿照抖音做一个评论功能,支持展开和收起, 首先我们需要对功能做一个拆解,评论区功能,两个模块,一个是发表评论模块,一个是评论展示区。接下来对这两个模块进行…...

js:创建一个基于vite 的React项目
相关文档 Vite 官方中文文档React 中文文档React RouterRedux 中文文档Ant Design 5.0Awesome React 创建vite react项目 pnpm create vite react-app --template react# 根据提示,执行命令 cd react-app pnpm install pnpm run dev项目结构 $ tree -L 1 . ├─…...

论文阅读_医疗知识图谱_GraphCare
英文名称: GraphCare: Enhancing Healthcare Predictions with Open-World Personalized Knowledge Graphs 中文名称: GraphCare:通过开放世界的个性化知识图增强医疗保健预测 文章: http://arxiv.org/abs/2305.12788 代码: https://github.com/pat-jj/GraphCare 作…...

Android 蓝牙开发( 四 )
前言 上一篇文章给大家分享了Kotlin版的Android蓝牙的基础知识和基础用法,不过上一篇都是一些零散碎片化的程序,,这一篇给大家分享Android蓝牙开发实战项目KotlinCompose的初步使用 效果演示 : Android Compose 蓝牙开发 Android蓝牙实战开发…...

涂鸦智能携手亚马逊云科技 共建“联合安全实验室” 为IoT发展护航
2023年8月31日,全球化IoT开发者平台涂鸦智能(NYSE: TUYA,HKEX: 2391)在“2023亚马逊云科技re:Inforce中国站”大会宣布与全球领先的云计算公司亚马逊云科技共同成立“联合安全实验室”,旨在加强IoT行业的安全合规能力与…...

Oracle21C--Windows卸载与安装
卸载方法: (1)WinR,输入services.msc,打开服务,把Oracle相关的服务全部停止运行(重要) (2)WinR,输入regedit,打开注册表,删除Oracle开…...

关于 MySQL、PostgresSQL、Mariadb 数据库2038千年虫问题
MySQL 测试时间:2023-8 启动MySQL服务后,将系统时间调制2038年01月19日03时14分07秒之后的日期,发现MySQL服务自动停止。 根据最新的MySQL源码(mysql-8.1.0)分析,sql/sql_parse.cc中依然存在2038年千年虫…...

Linux - Docker 安装使用 常用命令 教程
Docker 官方文档地址: Get Started | Docker 中文参考手册: https://docker_practice.gitee.io/zh-cn/ 1.什么是 Docker 1.1 官方定义 最新官网首页 # 1.官方介绍 - We have a complete container solution for you - no matter who you are and where you are on your contain…...
AtCoder Beginner Contest 318 G - Typical Path Problem 题解
G - Typical Path Problem 题目大意 给定一张 N N N 个点、 M M M 条边的简单无向图 G G G 和三个整数 A , B , C A,B,C A,B,C。 是否存在一条从顶点 A A A 到 C C C,且经过 B B B 的简单路径? 数据范围: 3 ≤ N ≤ 2 1 0 5 3\le …...

21.4 CSS 盒子模型
1. 边框样式 border-style属性: 指定元素的边框样式.常用属性值: - none: 无边框(默认值). - solid: 实线边框. - dotted: 点状边框. - dashed: 虚线边框. - double: 双线边框. - groove: 凹槽状边框. - ridge: 脊状边框. - inset: 内阴影边框. - outset: 外阴影边框.这些值可…...

MybatisPlus入门
MybatisPlus入门 1.MyBatis-Plus1.1 ORM介绍1.2 MyBatis-Plus介绍 2.代码链接数据库2.1 创建项目2.2 添加依赖2.3 链接数据库2.3.1 准备数据库2.3.2 链接数据库2.3.3 创建实体类 2.4 创建Mapper层2.5 创建Controller层2.6 浏览器访问测试 MybatisPlus官方网站: 官网…...

飞腾平台芯片测试固件(SFW)和开机启动log
一、说两句 最近公司飞腾产品越来越多了,FT-2000/4的D2000的X100的,最近又新出了E2000。越来越多新来的小孩儿开始加入到飞腾的调测试中,那么在他们实际的调试中会遇到很多的问题。在固件启动阶段有的板卡会有一些异常,有时我们需…...

【大数据实训】基于Hive的北京市天气系统分析报告(二)
博主介绍:✌全网粉丝6W,csdn特邀作者、博客专家、Java领域优质创作者,博客之星、掘金/华为云/阿里云/InfoQ等平台优质作者、专注于大数据技术领域和毕业项目实战✌ 🍅文末获取项目联系🍅 目录 1. 引言 1.1 项目背景 1 1.2 项目意义 1 2.…...
WPF列表样式
WPF的数据绑定系统自动生成列表项对象,为单个项应用所需的样式不是很容易。解决方案是ItemContainerStyle 属性。如果设置了ItemContainerStyle 属性,当创建列表项时,列表控件会将其向下传递给每个项。对于ListBox控件,每个项有Li…...

Android逆向学习(二)vscode进行双开与图标修改
Android逆向学习(二)vscode进行双开与图标修改 写在前面 这其实应该还是吾爱的第一个作业,但是写完上一个博客的时候已经比较晚了,如果继续敲机械键盘吵到室友,我怕我看不到明天的太阳,所以我决定分成两篇…...

一个基于YAPI接口生产代码的开源工具
前后端分离的开发模式是一种趋势,但如果缺少好的开发工具跟管理模式,会使得前后端开发人员相互等待,扯皮等问题。从而影响项目的交付进度。 通过实践摸索,YAPI是一款很适合前后端分离开发的协助工具。它以项目为维度,可…...

Redis 缓存穿透击穿和雪崩
一、说明 Redis 缓存的使用,极大的提升了应用程序的性能和效率,特别是数据查询方面。但同时,它也带来了一些问题。其中,最要害的问题,就是数据的一致性问题,从严格意义上讲,这个问题无解。如果对…...
【根据当天日期输出明天的日期(需对闰年做判定)。】2022-5-15
缘由根据当天日期输出明天的日期(需对闰年做判定)。日期类型结构体如下: struct data{ int year; int month; int day;};-编程语言-CSDN问答 struct mdata{ int year; int month; int day; }mdata; int 天数(int year, int month) {switch (month){case 1: case 3:…...
pam_env.so模块配置解析
在PAM(Pluggable Authentication Modules)配置中, /etc/pam.d/su 文件相关配置含义如下: 配置解析 auth required pam_env.so1. 字段分解 字段值说明模块类型auth认证类模块,负责验证用户身份&am…...

江苏艾立泰跨国资源接力:废料变黄金的绿色供应链革命
在华东塑料包装行业面临限塑令深度调整的背景下,江苏艾立泰以一场跨国资源接力的创新实践,重新定义了绿色供应链的边界。 跨国回收网络:废料变黄金的全球棋局 艾立泰在欧洲、东南亚建立再生塑料回收点,将海外废弃包装箱通过标准…...
Qwen3-Embedding-0.6B深度解析:多语言语义检索的轻量级利器
第一章 引言:语义表示的新时代挑战与Qwen3的破局之路 1.1 文本嵌入的核心价值与技术演进 在人工智能领域,文本嵌入技术如同连接自然语言与机器理解的“神经突触”——它将人类语言转化为计算机可计算的语义向量,支撑着搜索引擎、推荐系统、…...
生成 Git SSH 证书
🔑 1. 生成 SSH 密钥对 在终端(Windows 使用 Git Bash,Mac/Linux 使用 Terminal)执行命令: ssh-keygen -t rsa -b 4096 -C "your_emailexample.com" 参数说明: -t rsa&#x…...
css3笔记 (1) 自用
outline: none 用于移除元素获得焦点时默认的轮廓线 broder:0 用于移除边框 font-size:0 用于设置字体不显示 list-style: none 消除<li> 标签默认样式 margin: xx auto 版心居中 width:100% 通栏 vertical-align 作用于行内元素 / 表格单元格ÿ…...

20个超级好用的 CSS 动画库
分享 20 个最佳 CSS 动画库。 它们中的大多数将生成纯 CSS 代码,而不需要任何外部库。 1.Animate.css 一个开箱即用型的跨浏览器动画库,可供你在项目中使用。 2.Magic Animations CSS3 一组简单的动画,可以包含在你的网页或应用项目中。 3.An…...
CRMEB 中 PHP 短信扩展开发:涵盖一号通、阿里云、腾讯云、创蓝
目前已有一号通短信、阿里云短信、腾讯云短信扩展 扩展入口文件 文件目录 crmeb\services\sms\Sms.php 默认驱动类型为:一号通 namespace crmeb\services\sms;use crmeb\basic\BaseManager; use crmeb\services\AccessTokenServeService; use crmeb\services\sms\…...

三分算法与DeepSeek辅助证明是单峰函数
前置 单峰函数有唯一的最大值,最大值左侧的数值严格单调递增,最大值右侧的数值严格单调递减。 单谷函数有唯一的最小值,最小值左侧的数值严格单调递减,最小值右侧的数值严格单调递增。 三分的本质 三分和二分一样都是通过不断缩…...
【LeetCode】3309. 连接二进制表示可形成的最大数值(递归|回溯|位运算)
LeetCode 3309. 连接二进制表示可形成的最大数值(中等) 题目描述解题思路Java代码 题目描述 题目链接:LeetCode 3309. 连接二进制表示可形成的最大数值(中等) 给你一个长度为 3 的整数数组 nums。 现以某种顺序 连接…...