算法通关村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 缓存的使用,极大的提升了应用程序的性能和效率,特别是数据查询方面。但同时,它也带来了一些问题。其中,最要害的问题,就是数据的一致性问题,从严格意义上讲,这个问题无解。如果对…...

XCTF-web-easyupload
试了试php,php7,pht,phtml等,都没有用 尝试.user.ini 抓包修改将.user.ini修改为jpg图片 在上传一个123.jpg 用蚁剑连接,得到flag...

树莓派超全系列教程文档--(61)树莓派摄像头高级使用方法
树莓派摄像头高级使用方法 配置通过调谐文件来调整相机行为 使用多个摄像头安装 libcam 和 rpicam-apps依赖关系开发包 文章来源: http://raspberry.dns8844.cn/documentation 原文网址 配置 大多数用例自动工作,无需更改相机配置。但是,一…...
day52 ResNet18 CBAM
在深度学习的旅程中,我们不断探索如何提升模型的性能。今天,我将分享我在 ResNet18 模型中插入 CBAM(Convolutional Block Attention Module)模块,并采用分阶段微调策略的实践过程。通过这个过程,我不仅提升…...
深入浅出:JavaScript 中的 `window.crypto.getRandomValues()` 方法
深入浅出:JavaScript 中的 window.crypto.getRandomValues() 方法 在现代 Web 开发中,随机数的生成看似简单,却隐藏着许多玄机。无论是生成密码、加密密钥,还是创建安全令牌,随机数的质量直接关系到系统的安全性。Jav…...

华为OD机试-食堂供餐-二分法
import java.util.Arrays; import java.util.Scanner;public class DemoTest3 {public static void main(String[] args) {Scanner in new Scanner(System.in);// 注意 hasNext 和 hasNextLine 的区别while (in.hasNextLine()) { // 注意 while 处理多个 caseint a in.nextIn…...
Spring AI 入门:Java 开发者的生成式 AI 实践之路
一、Spring AI 简介 在人工智能技术快速迭代的今天,Spring AI 作为 Spring 生态系统的新生力量,正在成为 Java 开发者拥抱生成式 AI 的最佳选择。该框架通过模块化设计实现了与主流 AI 服务(如 OpenAI、Anthropic)的无缝对接&…...
代理篇12|深入理解 Vite中的Proxy接口代理配置
在前端开发中,常常会遇到 跨域请求接口 的情况。为了解决这个问题,Vite 和 Webpack 都提供了 proxy 代理功能,用于将本地开发请求转发到后端服务器。 什么是代理(proxy)? 代理是在开发过程中,前端项目通过开发服务器,将指定的请求“转发”到真实的后端服务器,从而绕…...
Python 包管理器 uv 介绍
Python 包管理器 uv 全面介绍 uv 是由 Astral(热门工具 Ruff 的开发者)推出的下一代高性能 Python 包管理器和构建工具,用 Rust 编写。它旨在解决传统工具(如 pip、virtualenv、pip-tools)的性能瓶颈,同时…...
Xen Server服务器释放磁盘空间
disk.sh #!/bin/bashcd /run/sr-mount/e54f0646-ae11-0457-b64f-eba4673b824c # 全部虚拟机物理磁盘文件存储 a$(ls -l | awk {print $NF} | cut -d. -f1) # 使用中的虚拟机物理磁盘文件 b$(xe vm-disk-list --multiple | grep uuid | awk {print $NF})printf "%s\n"…...
CSS设置元素的宽度根据其内容自动调整
width: fit-content 是 CSS 中的一个属性值,用于设置元素的宽度根据其内容自动调整,确保宽度刚好容纳内容而不会超出。 效果对比 默认情况(width: auto): 块级元素(如 <div>)会占满父容器…...