算法通关村第十五关:青铜-用4KB内存寻找重复元素
青铜挑战-用4KB内存寻找重复元素
位运算在查找元素中的妙用
题目要求:
给定一个数组,包含从1到N的整数,N最大为32000,数组可能还有重复值,且N的取值不定,若只有4KB的内存可用,该如何打印数组中所有重复元素。
思路分析
本题是非常典型的海量数据处理的问题,使用的是位运算结构
内存大小关系
1字节 = 1byte(拜特) = 1B = 8bit(比特,位)
1KB = 1024B
1MB = 1024KB
1GB = 1024MB
如果没有内存要求,创建一个大小为N的数组,然后将这些整数(32位)放进来,N最大为32000,则需要 320004B ≈ 128KB
如果只有4KB的空间,那么只能寻址 4KB = 4*1024B = 4*10248bit(比特) 该值大于32000
因此我们可以创建32000比特的位向量(比特数组),其中一个比特位置就代表一个整数,类似索引
利用这个位向量,就可以遍历访问整个数组。如果发现数组元素是v,那么就将位置为v的位设置为1,碰到重复元素,就输出一下
代码实现
1个数组元素存储 32 个数字信息,如索引为0的元素存储1~32
def check_duplicates(array):bitset = [0] * (32000 // 32)for num in array:num0 = num - 1if (bitset[num // 32] >> (num0 % 32)) & 1:print(num)else:bitset[num // 32] |= (1 << (num0 % 32))if __name__ == '__main__':check_duplicates([1, 2, 3, 2])
public class FindDuplicatesIn32000 {public void checkDuplicates(int[] array) {BitSet bs = new BitSet(32000);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);}}}static 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); // 求32的余数return (bitset[wordNumber] & (1 << bitNumber)) != 0;}void set(int pos) {int wordNumber = (pos >> 5);// 除以32int bitNumber = (pos & 0x1F);// 求32的余数bitset[wordNumber] |= 1 << bitNumber;}}
}
相关文章:
算法通关村第十五关:青铜-用4KB内存寻找重复元素
青铜挑战-用4KB内存寻找重复元素 位运算在查找元素中的妙用 题目要求: 给定一个数组,包含从1到N的整数,N最大为32000,数组可能还有重复值,且N的取值不定,若只有4KB的内存可用,该如何打印数组中…...

SQL注入 - 宽字节注入
文章目录 SQL注入 - 宽字节注入宽字节注入前置知识宽字节靶场实战判断是否存在SQL注入判断位数判显错位判库名判表名判列名 SQL注入 - 宽字节注入 靶场 sqli - labs less-32 宽字节注入主要是绕过魔术引号的,数据库解析中除了UTF-8编码外的所有编码如:G…...

Flink基础
Flink architecture job manager is master task managers are workers task slot is a unit of resource in cluster, number of slot is equal to number of cores(超线程则slot2*cores), slot一组内存一些线程共享CPU when starting a cluster,job manager will allocate a …...

javaee spring aop 注解实现
切面类 package com.test.advice;import org.aspectj.lang.ProceedingJoinPoint; import org.aspectj.lang.annotation.*;//切面类 Aspect public class MyAdvice {//定义切点表达式Pointcut("execution(* com.test.service.impl.*.add(..))")public void pc(){}//B…...

Qt应用开发(基础篇)——按钮基类 QAbstractButton
一、前言 QAbstractButton类,继承于QWidget,是Qt按钮小部件的抽象基类,提供按钮常用的功能。 QAbstractButton按钮基类,它的子类(pushbutton、checkbox、toolbutton等)处理用户操作,并指定按钮的绘制方式。QAbstractBu…...
2023年最新的 前端面试题(个人总结)
目录 vue 1.vue2 和 vue3 的区别 2.vue2 和 vue3的原理 3.组合式api 和 选项式api 3. Proxy和object.defineproperty 4..v-show 与 v-if 的区别 5.计算属性和 watcher 6.虚拟DOM 7.key的作用是什么? 8.v-if 和 v-for 的优先级是什么? 9.vuex …...
服务器基本故障排查方法
1、加电类故障 定义 从上电(或复位)到自检完成这一段过程中电脑所发生的故障。可能的故障现象 1、 主机不能加电(如:电源风扇不转或转一下即停等)、有时不能加电、开机掉闸、机箱金属部分带电等; 2、 开机无显,开机报警; 3、 自检报错或死机、自检过程中…...

docker从零部署jenkins保姆级教程
jenkins,基本是最常用的持续集成工具。在实际的工作中,后端研发一般没有jenkins的操作权限,只有一些查看权限,但是我们的代码是经过这个工具构建出来部署到服务器的,所以我觉着有必要了解一下这个工具的搭建过程以及简…...
什么是 MVVM 模式?
MVVM 模式 官方解释:Vue 虽然没有完全遵循 MVVM 模型,但是 Vue 的设计也受到了它的启发。因此在文档中经常会使用 vm (ViewModel 的缩写) 这个变量名表示 Vue 实例。 什么是 MVVM 模式? MVVM 是一种新的开发模式,对比传统模式&…...

WebGL Varing变量的作用和内插过程,及执行Varing时涉及的图形装配、光栅化、颜色插值、片元着色器执行机制等详解
目录 前言 在 WebGL 或 OpenGL 中,“varying” 是一种用于在顶点着色器和片元着色器之间传递数据的特殊类型的变量。它允许在顶点着色器对数据进行处理后,在片元着色器中使用该处理后的数据进行进一步计算。 彩色三个点 编辑 彩色三个点示例代码…...
赢在起跑线:战略定位咨询带来的核心价值
在企业的发展之路上,三个核心问题始终伴随着我们:我们是谁?我们要做什么?我们要如何做?在业务的马拉松比赛中,开始时的位置至关重要。而战略定位咨询就是帮助企业赢在起跑线的关键。那么什么是战略定位?战略定位包含…...

【链表OJ 11】复制带随机指针的链表
前言: 💥🎈个人主页:Dream_Chaser~ 🎈💥 ✨✨刷题专栏:http://t.csdn.cn/UlvTc ⛳⛳本篇内容:力扣上链表OJ题目 目录 leetcode138. 复制带随机指针的链表 1. 问题描述 2.代码思路: 2.1拷贝节点插入到…...

Jenkins自动构建(Gitee)
Gitee简介安装JenkinsCLI https://blog.csdn.net/tongxin_tongmeng/article/details/132632743 安装Gitee jenkins-cli install-plugin gitee:1.2.7 # https://plugins.jenkins.io/gitee/releases获取安装命令(稍作变更) JenkinsURL Dashboard-->配置-->Jenkins Locatio…...

nginx离线安装
ngixn的离线安装(centos7) 需要的依赖 gcc、gcc-c pcre-8.42.tar.gz zlib-1.2.11.tar.gz openssl-1.1.1s.tar.gz perl-5.28.0.tar.gz 在进行nginx离线安装时,首先查看系统是否安装 gcc、gcc-c,若没有进行安装,请先进行安装 gcc -v #查…...
Oracle Merge Into ORA-00001: unique constaint violated问题
最近使用Datax同步进行定时数据同步,并在同步完之后进行回调sql进行统计操作。对应的ORACLE表结构如下: create table DATA_STAT_DAY ( DATA_DATE DATE, ID VARCHAR2(2), NAME VARCHAR2(2), CLASSNO VARCHAR2(2), SCORES NUMBER(16,0) );CREATE UNIQU…...

javaScript:DOM中的CSS操作
目录 1.style 属性获取元素写在行间的样式 2.getComputedStyle(元素对象,null)可以获取元素的非行间样式 3.案例(定义一个div和按钮,每点击一次按钮div宽度增加) 效果预览图 代码实现 在 JavaScript 中,可以通过…...

2023最新UI工作室官网个人主页源码/背景音乐/随机壁纸/一言
2023最新UI工作室官网个人主页源码/支持背景音乐/随机壁纸/一言 功能介绍: 载入动画 站点简介 Hitokoto 一言 日期及时间 实时天气 时光进度条 音乐播放器 移动端适配 打开文件;index.html和setting.json修改替换你的相关信息&a…...

常用命令之mysql命令之show命令
一、mysql show命令简介 mysql数据库中show命令是一个非常实用的命令,SHOW命令用于显示MySQL数据库中的信息。它可以用于显示数据库、表、列、索引和用户等各种对象的信息。我们常用的有show databases,show tables,show full processlist等&…...
iOS接入IJKPlayer遇到的问题汇总
这里有一个我自己编译的IJKMediaFramework,能解决目前Github上反馈很多常见的IJKPlayer使用问题(包含播放异常,UI主线程Crash等),替换自己项目中的IJKMediaFramework即可链接: https://pan.baidu.com/s/1UO-YfN_1YIDOX81bgW8bag?pwdvq4u 提取…...

【LeetCode题目详解】第八章 贪心算法 part06 738.单调递增的数字 968.监控二叉树 (day37补)
本文章代码以c为例! 一、力扣第738题:单调递增的数字 题目: 当且仅当每个相邻位数上的数字 x 和 y 满足 x < y 时,我们称这个整数是单调递增的。 给定一个整数 n ,返回 小于或等于 n 的最大数字,且数…...
【Java学习笔记】Arrays类
Arrays 类 1. 导入包:import java.util.Arrays 2. 常用方法一览表 方法描述Arrays.toString()返回数组的字符串形式Arrays.sort()排序(自然排序和定制排序)Arrays.binarySearch()通过二分搜索法进行查找(前提:数组是…...

CentOS下的分布式内存计算Spark环境部署
一、Spark 核心架构与应用场景 1.1 分布式计算引擎的核心优势 Spark 是基于内存的分布式计算框架,相比 MapReduce 具有以下核心优势: 内存计算:数据可常驻内存,迭代计算性能提升 10-100 倍(文档段落:3-79…...
Robots.txt 文件
什么是robots.txt? robots.txt 是一个位于网站根目录下的文本文件(如:https://example.com/robots.txt),它用于指导网络爬虫(如搜索引擎的蜘蛛程序)如何抓取该网站的内容。这个文件遵循 Robots…...
鱼香ros docker配置镜像报错:https://registry-1.docker.io/v2/
使用鱼香ros一件安装docker时的https://registry-1.docker.io/v2/问题 一键安装指令 wget http://fishros.com/install -O fishros && . fishros出现问题:docker pull 失败 网络不同,需要使用镜像源 按照如下步骤操作 sudo vi /etc/docker/dae…...

让AI看见世界:MCP协议与服务器的工作原理
让AI看见世界:MCP协议与服务器的工作原理 MCP(Model Context Protocol)是一种创新的通信协议,旨在让大型语言模型能够安全、高效地与外部资源进行交互。在AI技术快速发展的今天,MCP正成为连接AI与现实世界的重要桥梁。…...
css3笔记 (1) 自用
outline: none 用于移除元素获得焦点时默认的轮廓线 broder:0 用于移除边框 font-size:0 用于设置字体不显示 list-style: none 消除<li> 标签默认样式 margin: xx auto 版心居中 width:100% 通栏 vertical-align 作用于行内元素 / 表格单元格ÿ…...

优选算法第十二讲:队列 + 宽搜 优先级队列
优选算法第十二讲:队列 宽搜 && 优先级队列 1.N叉树的层序遍历2.二叉树的锯齿型层序遍历3.二叉树最大宽度4.在每个树行中找最大值5.优先级队列 -- 最后一块石头的重量6.数据流中的第K大元素7.前K个高频单词8.数据流的中位数 1.N叉树的层序遍历 2.二叉树的锯…...
Python网页自动化Selenium中文文档
1. 安装 1.1. 安装 Selenium Python bindings 提供了一个简单的API,让你使用Selenium WebDriver来编写功能/校验测试。 通过Selenium Python的API,你可以非常直观的使用Selenium WebDriver的所有功能。 Selenium Python bindings 使用非常简洁方便的A…...

java高级——高阶函数、如何定义一个函数式接口类似stream流的filter
java高级——高阶函数、stream流 前情提要文章介绍一、函数伊始1.1 合格的函数1.2 有形的函数2. 函数对象2.1 函数对象——行为参数化2.2 函数对象——延迟执行 二、 函数编程语法1. 函数对象表现形式1.1 Lambda表达式1.2 方法引用(Math::max) 2 函数接口…...

五、jmeter脚本参数化
目录 1、脚本参数化 1.1 用户定义的变量 1.1.1 添加及引用方式 1.1.2 测试得出用户定义变量的特点 1.2 用户参数 1.2.1 概念 1.2.2 位置不同效果不同 1.2.3、用户参数的勾选框 - 每次迭代更新一次 总结用户定义的变量、用户参数 1.3 csv数据文件参数化 1、脚本参数化 …...