[Go版]算法通关村第十五关青铜——用4KB内存寻找重复元素
目录
- 题目:用4KB内存寻找重复元素
- 思路分析:使用位存储
- 如何存储这32000个整数?
- 每个整数对应在位图中的存储状态举例
- 如何判断是重复的?
- 具体的步骤
- 复杂度:时间复杂度 O ( n ) O(n) O(n)、空间复杂度 O ( 1 ) O(1) O(1)
- Go代码
在
海量数据
中,此时普通的数组、链表、Hash、树等等结构有无效了 ,因为内存空间放不下了。而常规的递归、排序,回溯、贪心和动态规划等思想也无效了,因为执行都会超时,必须另外想办法。这类问题该如何下手呢?这里介绍三种非常典型的思路:
使用位存储
,使用位存储最大的好处是占用的空间是简单存整数的1/8。例如一个40亿的整数数组,如果用整数存储需要16GB左右的空间,而如果使用位存储,就可以用2GB的空间,这样很多问题就能够解决了。如果文件实在太大 ,无法在内存中放下,则需要考虑将大文件分成若干小块,先处理每个块,最后再逐步得到想要的结果,这种方式也叫做
外部排序
。这样需要遍历全部序列至少两次,是典型的用时间换空间的方法。
堆
,如果在超大数据中找第K大、第K小,K个最大、K个最小,则特别适合使用堆来做。而且将超大数据换成流数据也可以,而且几乎是唯一的方式,口诀就是“查小用大堆,查大用小堆”。
常识补充:10亿 ≈ 1G、100万 ≈ 1M
题目:用4KB内存寻找重复元素
给定一个数组,包含从1到N的整数,N最大为32000,数组可能还有重复值,且N的取值不定,若只有4KB的内存可用,该如何打印数组中所有重复元素。
思路分析:使用位存储
如何存储这32000个整数?
常规思路分析:32000个整数,整数用int表示,一个int占用4个字节(byte)
,32000个整数所需内存就是 :
32000 * 4 = 128000(byte)
32000 * 4 / 1024 = 125(KB)
125(KB) > 4(KB) //可见,已经超过题目要求的4KB内存要求。
下面我们使用位存储
的方式:1个字节(byte)=8位(bit)
,32000个正数用32000个位就是:
32000 / 8 = 4000(byte)
32000 / 8 / 1024 = 3.9(KB)
3.9(KB)< 4(KB) //如此,就满足题意,使用了4KB就能存储32000个元素
每个整数对应在位图中的存储状态举例
原数据: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 ...
该值在位图中的索引值: 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 2 2 2 ...
该值在位图中的偏移量: 1 2 3 4 5 6 7 0 1 2 3 4 5 6 7 0 1 2 ...1 对应的位图值,和二进制值为:byteMap[0] 00000010
2 对应的位图值,和二进制值为:byteMap[0] 00000100
3 对应的位图值,和二进制值为:byteMap[0] 00001000
4 对应的位图值,和二进制值为:byteMap[0] 00010000
5 对应的位图值,和二进制值为:byteMap[0] 00100000
6 对应的位图值,和二进制值为:byteMap[0] 01000000
7 对应的位图值,和二进制值为:byteMap[0] 10000000
8 对应的位图值,和二进制值为:byteMap[1] 00000001
9 对应的位图值,和二进制值为:byteMap[1] 00000010
...
如何判断是重复的?
既然我们用一个位(bit)代表一个数值,那么该位的两种状态0或1,就可以用于判断该值是否存在。
例如:字节00001101
表示以下情况:
- 第 0 位(最低位)为 1,表示数字 1 出现过。
- 第 1 位为 0,表示数字 2 没有出现过。
- 第 2 位为 1,表示数字 3 出现过。
- 第 3 位为 1,表示数字 4 出现过。
- 后续位为 0,表示数字 5 到 8 都没有出现过。
mark := 1 << offset //offset 就是偏移量
if (bitmap[index] & mask) != 0 {// 位已经被设置,说明数字出现过
}
bitmap[index] |= mask //设置该位值为1
具体的步骤
位图(Bitmap)是一种数据结构,用于表示一组元素的状态或属性,通常用二进制位来表示,每个位代表一种状态或属性。在计算机科学中,位图被广泛用于各种应用,如图像处理、数据压缩、数据库索引等。
- 初始化位图:由于N最大是32000,可以是哦用一个长度为32000/8=4000的位图,每个位可以表示一个整数。
- 遍历数组,对于数组中的每个元素:
- 计算x在位图中的索引和位偏移。例如:x=5,则索引为5/8=0,位偏移为5%8=5。
- 检查位图的索引位置是否已经被标记。
- 如果未被标记,则将其标记为已访问;
- 如果已经被标记,则说明x是重复的,打印x。
- 打印重复元素。
复杂度:时间复杂度 O ( n ) O(n) O(n)、空间复杂度 O ( 1 ) O(1) O(1)
Go代码
源码地址: GitHub-golang版本(含单元测试代码)
func FindDuplicatesIn32000(arr []int) (duplicate []int) {N := 32000bitmap := make([]byte, N/8+1)for _, num := range arr {// 计算 num 在 bitmap 中的索引// index := num / 8index := num >> 3// 计算 num 在 bitmap 中的偏移量offset := num % 8mark := byte(1 << offset)if bitmap[index]&mark != 0 {duplicate = append(duplicate, num)} else {bitmap[index] |= mark}}return
}
或者
func FindDuplicatesIn32000(arr []int) (duplicate []int) {N := 32000// 或者这里不用+1,只要索引是base0的即可bitmap := make([]int, N/32)for _, num := range arr {num0 := num - 1 //base0开始index := num0 / 32offset := num0 % 32mark := 1 << offsetif bitmap[index]&mark != 0 {duplicate = append(duplicate, num)} else {bitmap[index] |= mark}}return
}
相关文章:
[Go版]算法通关村第十五关青铜——用4KB内存寻找重复元素
目录 题目:用4KB内存寻找重复元素思路分析:使用位存储如何存储这32000个整数?每个整数对应在位图中的存储状态举例如何判断是重复的?具体的步骤 复杂度:时间复杂度 O ( n ) O(n) O(n)、空间复杂度 O ( 1 ) O(1) O(1)Go…...

OJ练习第159题——消灭怪物的最大数量
消灭怪物的最大数量 力扣链接:1921. 消灭怪物的最大数量 题目描述 你正在玩一款电子游戏,在游戏中你需要保护城市免受怪物侵袭。给你一个 下标从 0 开始 且长度为 n 的整数数组 dist ,其中 dist[i] 是第 i 个怪物与城市的 初始距离&#…...
Prometheus-Rules(规则)
文章目录 一、介绍二、配置 Prometheus 使用规则文件三、 规则文件语法规则文件语法全局Recording rules(记录规则)2 Alerting rules(警报规则)3 模板化如何使用四、检查规则文件语法五、发送警报通知一、介绍 Prometheus规则是一种逻辑表达式,可用于定义有关监控数据的逻…...

打卡智能中国(六):村里出了“飞行员”
提起返乡青年,你的第一印象是什么?失败、躺平、卷不动了? 我们在浙江、福建、青海等地,参观一些农业智能化项目时,陪同参观的“飞手”,高兴地跟我们分享自己的心路历程: 在家门口做农业无人机操…...

自动化运维工具Ansible之playbooks剧本
自动化运维工具Ansible之playbooks剧本 一、playbooks1.playbooks简述2.playbooks剧本格式3.playbooks组成部分 二、实例1.编写脚本2.运行playbook3.定义、引用变量4.指定远程主机sudo切换用户5.when条件判断6.迭代7.Templates 模块8.tags 模块9.Roles 模块 三、编写应用模块1.…...

K8S访问控制------认证(authentication )、授权(authorization )、准入控制(admission control )体系
一、账号分类 在K8S体系中有两种账号类型:User accounts(用户账号),即针对human user的;Service accounts(服务账号),即针对pod的。这两种账号都可以访问 API server,都需要经历认证、授权、准入控制等步骤,相关逻辑图如下所示: 二、authentication (认证) 在…...

开开心心带你学习MySQL数据库之第三篇上
学校的项目组有必要加入吗? 看你的初心. ~~如果初心是通过这个经历能够提高自己的技术水平 ~~是可以考虑的 ~~如果初心是通过这个经历提高自己找工作的概率 ~~这个是不靠谱的,啥用没有 ~~如果初心是通过这个体验更美好的大学生活 ~~靠谱的 秋招,应届生,找工作是非常容易的!!! …...

Mysql批量插入大量数据的方法
使用存储过程进行插入, 在navicate中示例如下: 输入需要的参数点击完成 在begin end中输入代码,示例代码如下 CREATE DEFINERskip-grants userskip-grants host PROCEDURE batch_insert() BEGINdeclare i int default 0; set i0;while i<1…...

centos安装nginx实操记录(加安全配置)
1.下载与安装 yum -y install nginx2.启动命令 /usr/sbin/nginx -c /etc/nginx/nginx.conf3.新建配置文件 cd /etc/nginx/conf.d vim index.conf配了一个负责均衡,如不需要,可将 server localhost: 多余的去掉 upstream web_server{server localhost…...
【中等】49. 字母异位词分组
原题链接:https://leetcode.cn/problems/group-anagrams 49. 字母异位词分组 给你一个字符串数组,请你将 字母异位词 组合在一起。可以按任意顺序返回结果列表。 字母异位词 是由重新排列源单词的所有字母得到的一个新单词。 示例 1: 输入: strs [“…...

Python3 条件控制
Python3 条件控制 Python 条件语句是通过一条或多条语句的执行结果(True 或者 False)来决定执行的代码块。 可以通过下图来简单了解条件语句的执行过程: 代码执行过程: if 语句 Python中if语句的一般形式如下所示: if conditi…...

IDEA自定义模板
IDEA自定义模板 (1)定义sop模板 ①在Live Templates中增加模板 ②先定义一个模板的组 ③在模板组里新建模板 ④定义模板 Abbreviation:模板的缩略名称Description:模板的描述Template text:模板的代码片段应用范围。比如点击Define。选择如下&…...

【Unity3D】UI Toolkit简介
1 前言 UI Toolkit 是一种基于 Web 技术的 GUI 框架,是为了解决 UGUI 效率问题而设计的新一代 UI 系统(UGUI 的介绍详见→UGUI概述)。与 UGUI 不同,UI Toolkit 没有采用 GameObject 的方式,而是参考了 Web 技术的 XML …...

QT 界面相关操作
1> 创建自定义类时需要指定父类 2> 第一个界面的相关操作 #include "widget.h" #include<iostream> //printf #include<QDebug> //qDebuf #include<QIcon> //图标的头文件 using namespace std; //coutWidget::Widget(QWidget *…...
nestjs:docker build时执行npm install sharp提示downloading libvips socket hang up
问题: 如题 参考: sharp - High performance Node.js image processing 参考chinese-mirror处理 原因: 默认是从github上下载libvips库,但是使用socket协议,linux下不挂载梯子是无法加速的,因此得更换下镜像…...

图像分类学习笔记(七)——MobileNet
一、MobileNetV1 传统的神经网络,内存需求大、运算量大,导致无法在移动设备以及嵌入式设备上运行。之前的VGG16模型权重大小大概有490M,ResNet模型权重大小大概有644M。MobileNet网络是由google团队在2017年提出的,专注于移动端或…...

ssm+vue宠物领养系统源码和论文
ssmvue宠物领养系统源码和论文103 开发工具:idea 数据库mysql5.7 数据库链接工具:navcat,小海豚等 技术:ssm 摘 要 本课题是根据用户的需要以及网络的优势建立的一个宠物领养系统,来满足用宠物领养的需求。 本宠物领养系统…...
阜时科技联合客户发布全固态激光雷达面阵SPAD芯片及雷达整机
引言: 首先,我们非常荣幸受邀观摩此次行业盛会。阜时科技在全固态激光雷达面阵SPAD芯片研发上所取得的卓越成果,对于激光雷达大幅降本、扩大市场应用,具有重要意义。先划重点: 1,正式发布之前,阜时科技全固态激光雷达面阵SPAD芯片已被光之矩、武汉万集等多家激光雷达厂…...

leetcode 189. 轮转数组
2023.9.3 k的取值范围为0~100000,此时需要考虑到两种情况,当k为0时,此时数组不需要轮转,因此直接return返回;当k大于等于数组nums的大小时,数组将会转为原来的数组,然后再接着轮转,此…...

亚马逊广告收入突破百亿美元,有望成为下一个收入支柱来源?
据外媒报道,亚马逊新兴的广告业务已经价值数百亿美元,很可能成为其下一个收入支柱来源。 市场研究公司Insider Intelligence的分析师Andrew Lipsman表示,按照目前的发展轨迹,亚马逊广告业务甚至可以与其云计算业务相互抗衡。“毫…...
Java 语言特性(面试系列1)
一、面向对象编程 1. 封装(Encapsulation) 定义:将数据(属性)和操作数据的方法绑定在一起,通过访问控制符(private、protected、public)隐藏内部实现细节。示例: public …...

工业安全零事故的智能守护者:一体化AI智能安防平台
前言: 通过AI视觉技术,为船厂提供全面的安全监控解决方案,涵盖交通违规检测、起重机轨道安全、非法入侵检测、盗窃防范、安全规范执行监控等多个方面,能够实现对应负责人反馈机制,并最终实现数据的统计报表。提升船厂…...

8k长序列建模,蛋白质语言模型Prot42仅利用目标蛋白序列即可生成高亲和力结合剂
蛋白质结合剂(如抗体、抑制肽)在疾病诊断、成像分析及靶向药物递送等关键场景中发挥着不可替代的作用。传统上,高特异性蛋白质结合剂的开发高度依赖噬菌体展示、定向进化等实验技术,但这类方法普遍面临资源消耗巨大、研发周期冗长…...

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

Cinnamon修改面板小工具图标
Cinnamon开始菜单-CSDN博客 设置模块都是做好的,比GNOME简单得多! 在 applet.js 里增加 const Settings imports.ui.settings;this.settings new Settings.AppletSettings(this, HTYMenusonichy, instance_id); this.settings.bind(menu-icon, menu…...

高危文件识别的常用算法:原理、应用与企业场景
高危文件识别的常用算法:原理、应用与企业场景 高危文件识别旨在检测可能导致安全威胁的文件,如包含恶意代码、敏感数据或欺诈内容的文档,在企业协同办公环境中(如Teams、Google Workspace)尤为重要。结合大模型技术&…...
【git】把本地更改提交远程新分支feature_g
创建并切换新分支 git checkout -b feature_g 添加并提交更改 git add . git commit -m “实现图片上传功能” 推送到远程 git push -u origin feature_g...
在web-view 加载的本地及远程HTML中调用uniapp的API及网页和vue页面是如何通讯的?
uni-app 中 Web-view 与 Vue 页面的通讯机制详解 一、Web-view 简介 Web-view 是 uni-app 提供的一个重要组件,用于在原生应用中加载 HTML 页面: 支持加载本地 HTML 文件支持加载远程 HTML 页面实现 Web 与原生的双向通讯可用于嵌入第三方网页或 H5 应…...

深度学习习题2
1.如果增加神经网络的宽度,精确度会增加到一个特定阈值后,便开始降低。造成这一现象的可能原因是什么? A、即使增加卷积核的数量,只有少部分的核会被用作预测 B、当卷积核数量增加时,神经网络的预测能力会降低 C、当卷…...

HarmonyOS运动开发:如何用mpchart绘制运动配速图表
##鸿蒙核心技术##运动开发##Sensor Service Kit(传感器服务)# 前言 在运动类应用中,运动数据的可视化是提升用户体验的重要环节。通过直观的图表展示运动过程中的关键数据,如配速、距离、卡路里消耗等,用户可以更清晰…...