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

[Go版]算法通关村第十五关青铜——用4KB内存寻找重复元素

目录

海量数据中,此时普通的数组、链表、Hash、树等等结构有无效了 ,因为内存空间放不下了。而常规的递归、排序,回溯、贪心和动态规划等思想也无效了,因为执行都会超时,必须另外想办法。这类问题该如何下手呢?这里介绍三种非常典型的思路:

  1. 使用位存储,使用位存储最大的好处是占用的空间是简单存整数的1/8。例如一个40亿的整数数组,如果用整数存储需要16GB左右的空间,而如果使用位存储,就可以用2GB的空间,这样很多问题就能够解决了。

  2. 如果文件实在太大 ,无法在内存中放下,则需要考虑将大文件分成若干小块,先处理每个块,最后再逐步得到想要的结果,这种方式也叫做外部排序。这样需要遍历全部序列至少两次,是典型的用时间换空间的方法

  3. 如果在超大数据中找第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)是一种数据结构,用于表示一组元素的状态或属性,通常用二进制位来表示,每个位代表一种状态或属性。在计算机科学中,位图被广泛用于各种应用,如图像处理、数据压缩、数据库索引等。

  1. 初始化位图:由于N最大是32000,可以是哦用一个长度为32000/8=4000的位图,每个位可以表示一个整数。
  2. 遍历数组,对于数组中的每个元素:
    • 计算x在位图中的索引和位偏移。例如:x=5,则索引为5/8=0,位偏移为5%8=5。
    • 检查位图的索引位置是否已经被标记。
      • 如果未被标记,则将其标记为已访问;
      • 如果已经被标记,则说明x是重复的,打印x。
  3. 打印重复元素。

复杂度:时间复杂度 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内存寻找重复元素

目录 题目&#xff1a;用4KB内存寻找重复元素思路分析&#xff1a;使用位存储如何存储这32000个整数&#xff1f;每个整数对应在位图中的存储状态举例如何判断是重复的&#xff1f;具体的步骤 复杂度&#xff1a;时间复杂度 O ( n ) O(n) O(n)、空间复杂度 O ( 1 ) O(1) O(1)Go…...

OJ练习第159题——消灭怪物的最大数量

消灭怪物的最大数量 力扣链接&#xff1a;1921. 消灭怪物的最大数量 题目描述 你正在玩一款电子游戏&#xff0c;在游戏中你需要保护城市免受怪物侵袭。给你一个 下标从 0 开始 且长度为 n 的整数数组 dist &#xff0c;其中 dist[i] 是第 i 个怪物与城市的 初始距离&#…...

Prometheus-Rules(规则)

文章目录 一、介绍二、配置 Prometheus 使用规则文件三、 规则文件语法规则文件语法全局Recording rules(记录规则)2 Alerting rules(警报规则)3 模板化如何使用四、检查规则文件语法五、发送警报通知一、介绍 Prometheus规则是一种逻辑表达式,可用于定义有关监控数据的逻…...

打卡智能中国(六):村里出了“飞行员”

提起返乡青年&#xff0c;你的第一印象是什么&#xff1f;失败、躺平、卷不动了&#xff1f; 我们在浙江、福建、青海等地&#xff0c;参观一些农业智能化项目时&#xff0c;陪同参观的“飞手”&#xff0c;高兴地跟我们分享自己的心路历程&#xff1a; 在家门口做农业无人机操…...

自动化运维工具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批量插入大量数据的方法

使用存储过程进行插入&#xff0c; 在navicate中示例如下&#xff1a; 输入需要的参数点击完成 在begin end中输入代码&#xff0c;示例代码如下 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配了一个负责均衡&#xff0c;如不需要&#xff0c;可将 server localhost: 多余的去掉 upstream web_server{server localhost…...

【中等】49. 字母异位词分组

原题链接&#xff1a;https://leetcode.cn/problems/group-anagrams 49. 字母异位词分组 给你一个字符串数组&#xff0c;请你将 字母异位词 组合在一起。可以按任意顺序返回结果列表。 字母异位词 是由重新排列源单词的所有字母得到的一个新单词。 示例 1: 输入: strs [“…...

Python3 条件控制

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

IDEA自定义模板

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

【Unity3D】UI Toolkit简介

1 前言 UI Toolkit 是一种基于 Web 技术的 GUI 框架&#xff0c;是为了解决 UGUI 效率问题而设计的新一代 UI 系统&#xff08;UGUI 的介绍详见→UGUI概述&#xff09;。与 UGUI 不同&#xff0c;UI Toolkit 没有采用 GameObject 的方式&#xff0c;而是参考了 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

问题&#xff1a; 如题 参考&#xff1a; sharp - High performance Node.js image processing 参考chinese-mirror处理 原因&#xff1a; 默认是从github上下载libvips库&#xff0c;但是使用socket协议&#xff0c;linux下不挂载梯子是无法加速的&#xff0c;因此得更换下镜像…...

图像分类学习笔记(七)——MobileNet

一、MobileNetV1 传统的神经网络&#xff0c;内存需求大、运算量大&#xff0c;导致无法在移动设备以及嵌入式设备上运行。之前的VGG16模型权重大小大概有490M&#xff0c;ResNet模型权重大小大概有644M。MobileNet网络是由google团队在2017年提出的&#xff0c;专注于移动端或…...

ssm+vue宠物领养系统源码和论文

ssmvue宠物领养系统源码和论文103 开发工具&#xff1a;idea 数据库mysql5.7 数据库链接工具&#xff1a;navcat,小海豚等 技术&#xff1a;ssm 摘 要 本课题是根据用户的需要以及网络的优势建立的一个宠物领养系统&#xff0c;来满足用宠物领养的需求。 本宠物领养系统…...

阜时科技联合客户发布全固态激光雷达面阵SPAD芯片及雷达整机

引言: 首先,我们非常荣幸受邀观摩此次行业盛会。阜时科技在全固态激光雷达面阵SPAD芯片研发上所取得的卓越成果,对于激光雷达大幅降本、扩大市场应用,具有重要意义。先划重点: 1,正式发布之前,阜时科技全固态激光雷达面阵SPAD芯片已被光之矩、武汉万集等多家激光雷达厂…...

leetcode 189. 轮转数组

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

亚马逊广告收入突破百亿美元,有望成为下一个收入支柱来源?

据外媒报道&#xff0c;亚马逊新兴的广告业务已经价值数百亿美元&#xff0c;很可能成为其下一个收入支柱来源。 市场研究公司Insider Intelligence的分析师Andrew Lipsman表示&#xff0c;按照目前的发展轨迹&#xff0c;亚马逊广告业务甚至可以与其云计算业务相互抗衡。“毫…...

UE5 学习系列(二)用户操作界面及介绍

这篇博客是 UE5 学习系列博客的第二篇&#xff0c;在第一篇的基础上展开这篇内容。博客参考的 B 站视频资料和第一篇的链接如下&#xff1a; 【Note】&#xff1a;如果你已经完成安装等操作&#xff0c;可以只执行第一篇博客中 2. 新建一个空白游戏项目 章节操作&#xff0c;重…...

MFC内存泄露

1、泄露代码示例 void X::SetApplicationBtn() {CMFCRibbonApplicationButton* pBtn GetApplicationButton();// 获取 Ribbon Bar 指针// 创建自定义按钮CCustomRibbonAppButton* pCustomButton new CCustomRibbonAppButton();pCustomButton->SetImage(IDB_BITMAP_Jdp26)…...

在rocky linux 9.5上在线安装 docker

前面是指南&#xff0c;后面是日志 sudo dnf config-manager --add-repo https://download.docker.com/linux/centos/docker-ce.repo sudo dnf install docker-ce docker-ce-cli containerd.io -y docker version sudo systemctl start docker sudo systemctl status docker …...

深入浅出:JavaScript 中的 `window.crypto.getRandomValues()` 方法

深入浅出&#xff1a;JavaScript 中的 window.crypto.getRandomValues() 方法 在现代 Web 开发中&#xff0c;随机数的生成看似简单&#xff0c;却隐藏着许多玄机。无论是生成密码、加密密钥&#xff0c;还是创建安全令牌&#xff0c;随机数的质量直接关系到系统的安全性。Jav…...

Map相关知识

数据结构 二叉树 二叉树&#xff0c;顾名思义&#xff0c;每个节点最多有两个“叉”&#xff0c;也就是两个子节点&#xff0c;分别是左子 节点和右子节点。不过&#xff0c;二叉树并不要求每个节点都有两个子节点&#xff0c;有的节点只 有左子节点&#xff0c;有的节点只有…...

什么是Ansible Jinja2

理解 Ansible Jinja2 模板 Ansible 是一款功能强大的开源自动化工具&#xff0c;可让您无缝地管理和配置系统。Ansible 的一大亮点是它使用 Jinja2 模板&#xff0c;允许您根据变量数据动态生成文件、配置设置和脚本。本文将向您介绍 Ansible 中的 Jinja2 模板&#xff0c;并通…...

Java线上CPU飙高问题排查全指南

一、引言 在Java应用的线上运行环境中&#xff0c;CPU飙高是一个常见且棘手的性能问题。当系统出现CPU飙高时&#xff0c;通常会导致应用响应缓慢&#xff0c;甚至服务不可用&#xff0c;严重影响用户体验和业务运行。因此&#xff0c;掌握一套科学有效的CPU飙高问题排查方法&…...

Netty从入门到进阶(二)

二、Netty入门 1. 概述 1.1 Netty是什么 Netty is an asynchronous event-driven network application framework for rapid development of maintainable high performance protocol servers & clients. Netty是一个异步的、基于事件驱动的网络应用框架&#xff0c;用于…...

MFC 抛体运动模拟:常见问题解决与界面美化

在 MFC 中开发抛体运动模拟程序时,我们常遇到 轨迹残留、无效刷新、视觉单调、物理逻辑瑕疵 等问题。本文将针对这些痛点,详细解析原因并提供解决方案,同时兼顾界面美化,让模拟效果更专业、更高效。 问题一:历史轨迹与小球残影残留 现象 小球运动后,历史位置的 “残影”…...

莫兰迪高级灰总结计划简约商务通用PPT模版

莫兰迪高级灰总结计划简约商务通用PPT模版&#xff0c;莫兰迪调色板清新简约工作汇报PPT模版&#xff0c;莫兰迪时尚风极简设计PPT模版&#xff0c;大学生毕业论文答辩PPT模版&#xff0c;莫兰迪配色总结计划简约商务通用PPT模版&#xff0c;莫兰迪商务汇报PPT模版&#xff0c;…...