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

算法通过村第十五关-超大规模|青铜笔记|海量找数

文章目录

  • 前言
  • 用4KB内存寻找重复数
  • 总结


前言


提示:并不是所有黑暗的地方,都需要光明。 --珍妮特·温特森《句子不是唯一的水果》

在大部分算法中,默认给点给的数据量都是很小的,例如只有几个或者十几个元素,但是如果遇到了相当大的数据量高达百万乃至十亿,那么处理逻辑就会发生很大差异,也就是说算法中常考的,这个很重要。

这里的题目重点是理解怎么处理,面试的时候遇上可以不用慌张,做到心中有数,这一半也不会写代码。这里做如下演示:

在海量数据中,此时普通的数组、链表、Hash、树等等结构这里就没有什么效果了,因为内存空间肯定是放不下的。而常规的递归、排序、回溯、贪心甚至动态规划等思想在大量数据面前也是不顶用的。因为执行超时,必然要另寻他法。这类问题我们要如何下手呢?这里又三种比较今典的思路:

  1. 使用位存储,使用存储最大的好处是占用空间是简单存储整数的 1/8 。例如一个 40亿的整数数组,如果用整数存储需要 16GB 左右的空间,而如果使用位存储,就可以仅用 0.5GB 的空间,这样很多问题就能够解决了。
  2. 如果文件实在太大,无法在能存中存放,则需要考虑将大文件分成若干小块,先处理每块的,最后支部得到想要的结果,这种方式也叫做 外部排序。 这样需要遍历全部遍历至少两次,是经典的用时间换空间的方法。
  3. 。 在处理超大数据中找第K大,第K小,K个最大,K个最小。则特别使用堆来做。而且将超大数据换成流数据也是可以的,而且几乎是唯一的方式,口诀就是“查小用大堆,查大用小堆”。

用4KB内存寻找重复数

题目要求:给定一个数组,包含1到N的整数,N最大为32_000,数组可能还有重复值,且N的值取值不定,若只有4KB的内存可用,该如何打印数组中所有重复的元素。

分析:本身是一道海量数据问题的热身题目,如果去掉只用“4KB”的要求,我们可以先创建一个大小为N的数组,然后将这些数据放进去,但是整数最大为32_000。如果直接才用数组,则需要使用32_000 * 4B = 128KB的空间,而题目只有4kb 的内存限制,我们就必须先解决该如何存放的问题。

如果是只有4KB,那么考虑寻值,只能有 8 * 4 * 2 ^10 个比特。这个值要比32_000要大的多,因此我们可以创建一个32_000比特的维向量(比特数组),其中一个比特位位置就代表一个整数。利用这个位相量,就可以遍历整个数组,如果返现数组元素是v 那么将这个位置的v设置为1,碰到重复元素,就输出一下。

  /*** 检查重复项* @param array*/public void checkDuplicates(int[] array){BitSet bs = new BitSet(32_000);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];}public boolean get(int pos){int wordNumber = (pos >> 5); // 除以32int bitNumber = (pos & 0x1F); // 除以32return (bitSet[bitNumber] & (1 << bitNumber)) != 0;}public void set(int pos){int wordNumber = (pos >> 5); // 除以32int bitNumber = (pos & 0x1F); // 除以32bitSet[wordNumber] |= 1 << bitNumber;}}

总结

提示:海量数据去重;大数据筛选;海量找数;流数据过滤;堆的应用

在这里插入图片描述


如果有帮助到你,请给题解点个赞和收藏,让更多的人看到 ~ ("▔□▔)/

如有不理解的地方,欢迎你在评论区给我留言,我都会逐一回复 ~

也欢迎你 关注我 ,喜欢交朋友,喜欢一起探讨问题。

相关文章:

算法通过村第十五关-超大规模|青铜笔记|海量找数

文章目录 前言用4KB内存寻找重复数总结 前言 提示&#xff1a;并不是所有黑暗的地方&#xff0c;都需要光明。 --珍妮特温特森《句子不是唯一的水果》 在大部分算法中&#xff0c;默认给点给的数据量都是很小的&#xff0c;例如只有几个或者十几个元素&#xff0c;但是如果遇到…...

TCP、IP和HTTP的区别和联系

TCP&#xff08;Transmission Control Protocol&#xff09; TCP是一种面向连接的协议&#xff0c;负责数据的可靠性传输。它提供了错误检测和纠正、数据分段和重新组装、流量控制和拥塞控制等功能&#xff0c;最终确保数据可靠滴从一个端点传输到另一个端点。 TCP建立连接、传…...

【4】c++11新特性(稳定性和兼容性)—>final关键字

c中增加了final关键字来限制某个类不能被继承&#xff0c;或者某个虚函数不能被重写。如果使用final修饰函数&#xff0c;只能修饰虚函数&#xff0c;并且放在类或者函数的后面。 修饰函数 #include <iostream> using namespace std;class Base { public:virtual void t…...

23基于MATLAB的小波降噪,默认阈值消噪,强制消噪,给定软阈值消噪方法,数据直接替换后就可以跑。

基于MATLAB的小波降噪&#xff0c;默认阈值消噪&#xff0c;强制消噪&#xff0c;给定软阈值消噪方法&#xff0c;数据直接替换后就可以跑。 https://www.xiaohongshu.com/explore/652d57c600000...

蓝桥杯 常用STL (C++) 未完待续

动态数组 有些时候想开一个数组&#xff0c;但是却不知道应该开多大长度的数组合适&#xff0c;因为我们需要用到的数组可能会根据情况变动。 这时候我们就需要用到动态数组。所谓动态数组&#xff0c;也就是不定长数组&#xff0c;数组的长度是可以根据我们的需要动态改变的。…...

class id

在HTML和CSS中&#xff0c;"class" 和 "id" 是用于标识和定制元素的两种重要属性。 Class&#xff08;类&#xff09;: "class" 属性用于标识一个或多个HTML元素&#xff0c;允许你为它们应用相同的样式规则。可以将相同的类应用于多个不同元素。…...

Qt (QInputDialog 、QMessageBox、QMessageBox)对话框实战

目录 一、QInputDialog 类(输入对话框) 二、QMessageBox 类(消息框) 三、QMessageBox 类(自定义消息框) 一、QInputDialog 类(输入对话框) QInputDialog 是一个提供输入对话框的 Qt 类。它允许用户输入文本&#xff0c;并提供给用户选择可用选项的选项列表。QInputDialog 可…...

Java 解析 cURL(bash) 命令

解析 cURL&#xff08;bash&#xff09; 命令 1. 主要用于解析从浏览器复制来的 cURL(bash)2. 废话不多说&#xff0c;都在&#x1f37b;代码里了。参考资料 1. 主要用于解析从浏览器复制来的 cURL(bash) curl https://eva2.csdn.net/v3/06981375190026432f77c01bfca33e32/lts/…...

JDK21的虚拟线程是什么?和平台线程什么关系?

虚拟线程&#xff08;Virtual Thread&#xff09;是 JDK 而不是 OS 实现的轻量级线程(Lightweight Process&#xff0c;LWP&#xff09;&#xff0c;由 JVM 调度。许多虚拟线程共享同一个操作系统线程&#xff0c;虚拟线程的数量可以远大于操作系统线程的数量。 在引入虚拟线程…...

Unity DOTS Component概述

最近DOTS终于发布了正式的版本, 我们来分享以下DOTS里面地几个关键概念&#xff0c;方便大家上手学习掌握Unity DOTS开发。 Unity DOTS 中Entity作为实体不直接去存放数据&#xff0c;而是将数据以一个个的组件为载体来存放起来。每个Entity会得到一些不同的ComponentData的组…...

element ui 下拉框 选择月份和天数

一、背景 目前做的管理系统项目&#xff0c;期望实现功能为&#xff1a;设置出账周期和出账日&#xff0c;考虑使用element ui下拉框实现功能 二、所用技术 vue2element ui 三、实现效果 四、具体代码 <template><popup-frame :title"批量设置出账日" …...

用Java包com.sun.net.httpserver下面的类实现一个简单的http服务器demo

java的com.sun.net.httpserver包下的类提供了一个高层级的http服务器API&#xff0c;可以用来构建内嵌的http服务器。支持http和https。这些API提供了一个RFC 2616 (HTTP 1.1)和RFC 2818 (HTTP over TLS)的部分实现。 https://docs.oracle.com/en/java/javase/19/docs/api/jdk.…...

unity 浏览器插件【embedded browser(原zfbrowser)】简单教程,使unity支持web h5页面,附软件下载链接

一 简介 这是个在项目中使用了很久的浏览器插件。 很负责任的说这是在pc平台上最好用的浏览器插件 商业付费价格78刀&#xff0c;相比3d webview等插件动不动就178、368的价格就显得很良心 最新版下载链接&#xff08;请勿商用&#xff09; 1.1 功能概述 基本和普通浏览器无…...

LeetCode算法位运算—只出现一次的数字

目录 136. 只出现一次的数字 - 力扣&#xff08;LeetCode&#xff09; 解题思路&#xff1a; 代码&#xff1a; 运行结果&#xff1a; 补充 异或的重要性质 136. 只出现一次的数字 - 力扣&#xff08;LeetCode&#xff09; 给你一个 非空 整数数组 nums &#xff0c;除了某…...

vcpkg manifest 的使用

最近项目上要使用 CMakeLists 管理&#xff0c;由于 Windows 版本有依赖到 vcpkg 提供的库&#xff0c;所以需要使用 vcpkg manifest 来统一设置库的版本&#xff0c;方便后续维护 推荐一个文章&#xff0c;介绍的可以说是非常全面了 VCPKG 特性 - Versioning 不过里面也有一些…...

选择什么电容笔比较好?平板手写笔推荐

由于苹果Pencil的热销&#xff0c;让华国内市场上&#xff0c;也出现了不少的平替式电容笔&#xff0c;这些产品&#xff0c;有好有坏&#xff0c;价格也很公道。不过&#xff0c;也有很多产品的价格都很平价。我是一个拥有多年经验的数码发烧友&#xff0c;在前几年就开始用上…...

pdf转二维码怎么做?pdf二维码制作简单技巧

pdf是一种很常见的文件储存格式&#xff0c;一般通知、发票、简历都会保存为这种格式来使用&#xff0c;那么需要将pdf格式文件做成二维码&#xff0c;该用什么方式来制作呢&#xff1f;下面给大家分享一个pdf转二维码的在线工具&#xff0c;可以通过上传文件一键生成二维码&am…...

【CANoe】TX Self-ACK自应答配置与CPAL实现

一、引言 在测试CAN&CANFD通信或者网络管理的时候&#xff0c;我们经常遇到使用报文&#xff08;网络管理报文或者通信报文&#xff09;唤醒被测件这个测试点&#xff0c;如果测试比较多的情况下&#xff0c;我们就会发现&#xff0c;如果CANoe没有接被测件或者被测件没有…...

(Python)MATLAB mat矩阵和Python npy矩阵转换

Python np.ndarray矩阵转换为MATLAB mat文件 import numpy as npimport scipy.io as iomat_path mat_save_pathmat np.zeros([6, 128])io.savemat(mat_path, {name: mat})Python读取MATLAB mat文件 import numpy as np from scipy import iomat io.loadmat(your_mat_file.…...

Flink1.14 SourceReader概念入门讲解与源码解析 (三)

目录 SourceReader 概念 SourceReader 源码方法 void start(); InputStatus pollNext(ReaderOutput output) throws Exception; List snapshotState(long checkpointId); CompletableFuture isAvailable(); void addSplits(List splits); 参考 SourceReader 概念 Sour…...

Android Wi-Fi 连接失败日志分析

1. Android wifi 关键日志总结 (1) Wi-Fi 断开 (CTRL-EVENT-DISCONNECTED reason3) 日志相关部分&#xff1a; 06-05 10:48:40.987 943 943 I wpa_supplicant: wlan0: CTRL-EVENT-DISCONNECTED bssid44:9b:c1:57:a8:90 reason3 locally_generated1解析&#xff1a; CTR…...

日语AI面试高效通关秘籍:专业解读与青柚面试智能助攻

在如今就业市场竞争日益激烈的背景下&#xff0c;越来越多的求职者将目光投向了日本及中日双语岗位。但是&#xff0c;一场日语面试往往让许多人感到步履维艰。你是否也曾因为面试官抛出的“刁钻问题”而心生畏惧&#xff1f;面对生疏的日语交流环境&#xff0c;即便提前恶补了…...

linux之kylin系统nginx的安装

一、nginx的作用 1.可做高性能的web服务器 直接处理静态资源&#xff08;HTML/CSS/图片等&#xff09;&#xff0c;响应速度远超传统服务器类似apache支持高并发连接 2.反向代理服务器 隐藏后端服务器IP地址&#xff0c;提高安全性 3.负载均衡服务器 支持多种策略分发流量…...

定时器任务——若依源码分析

分析util包下面的工具类schedule utils&#xff1a; ScheduleUtils 是若依中用于与 Quartz 框架交互的工具类&#xff0c;封装了定时任务的 创建、更新、暂停、删除等核心逻辑。 createScheduleJob createScheduleJob 用于将任务注册到 Quartz&#xff0c;先构建任务的 JobD…...

现代密码学 | 椭圆曲线密码学—附py代码

Elliptic Curve Cryptography 椭圆曲线密码学&#xff08;ECC&#xff09;是一种基于有限域上椭圆曲线数学特性的公钥加密技术。其核心原理涉及椭圆曲线的代数性质、离散对数问题以及有限域上的运算。 椭圆曲线密码学是多种数字签名算法的基础&#xff0c;例如椭圆曲线数字签…...

Linux --进程控制

本文从以下五个方面来初步认识进程控制&#xff1a; 目录 进程创建 进程终止 进程等待 进程替换 模拟实现一个微型shell 进程创建 在Linux系统中我们可以在一个进程使用系统调用fork()来创建子进程&#xff0c;创建出来的进程就是子进程&#xff0c;原来的进程为父进程。…...

USB Over IP专用硬件的5个特点

USB over IP技术通过将USB协议数据封装在标准TCP/IP网络数据包中&#xff0c;从根本上改变了USB连接。这允许客户端通过局域网或广域网远程访问和控制物理连接到服务器的USB设备&#xff08;如专用硬件设备&#xff09;&#xff0c;从而消除了直接物理连接的需要。USB over IP的…...

AI病理诊断七剑下天山,医疗未来触手可及

一、病理诊断困局&#xff1a;刀尖上的医学艺术 1.1 金标准背后的隐痛 病理诊断被誉为"诊断的诊断"&#xff0c;医生需通过显微镜观察组织切片&#xff0c;在细胞迷宫中捕捉癌变信号。某省病理质控报告显示&#xff0c;基层医院误诊率达12%-15%&#xff0c;专家会诊…...

springboot整合VUE之在线教育管理系统简介

可以学习到的技能 学会常用技术栈的使用 独立开发项目 学会前端的开发流程 学会后端的开发流程 学会数据库的设计 学会前后端接口调用方式 学会多模块之间的关联 学会数据的处理 适用人群 在校学生&#xff0c;小白用户&#xff0c;想学习知识的 有点基础&#xff0c;想要通过项…...

在 Spring Boot 中使用 JSP

jsp&#xff1f; 好多年没用了。重新整一下 还费了点时间&#xff0c;记录一下。 项目结构&#xff1a; pom: <?xml version"1.0" encoding"UTF-8"?> <project xmlns"http://maven.apache.org/POM/4.0.0" xmlns:xsi"http://ww…...