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

【数据结构学习笔记】19:跳表(Skip List)

介绍

跳表是一个能在 O ( n l o g n ) O(nlogn) O(nlogn)时间完成查找、插入、删除的数据结构,相比于树形结构优点就是很好写(所以也用于实现Redis ZSet)。其核心思想就是维护一个元素有序的,能随机提升索引层数的链表。最下面一层就是一个普通的链表,存了所有的元素,而每次提升索引高度都一定会从最下面一层开始提升连续的若干层,因此从最上面的层到最下面的层,索引一定是从稀疏到稠密,所以在查询的时候就能从上层开始,很快的跳过一些元素,再向下一层走,逐渐定位到元素的位置。

实现思路

结构

固定跳表层数后,跳表的每个结点(存某个元素)都在每一层有一个next指针,指向这一层的下一个结点。

为了查询方便,设定一个虚拟头结点,这个虚拟头节点作为查询的起始节点,每一层会指向实际的这一层的起始节点。

内部操作:find

引入一个特殊的内部操作,用于定位结点在每一层的位置,不管是接下来要删除这个结点,还是在这个结点附近(前或者后)插入一个元素结点都能借用这个操作方便的找到它。

考虑到每一层都是一个单向链表,所以find操作一定是返回目标结点在每一层的前置结点。

因为这个操作希望得到的是一个Node指针的数组,这个数组会在下一步的操作(插入/删除/查询)中被用到,所以可以给这个跳表引入一个prev数组缓存这个信息,每次使用前直接清空就可以了。

查询操作:search

find得到目标元素的prev数组,然后就能找到最下面那层的结点,即prev[0]->next[0],根据结点是否存在以及是否是要找的元素就可以得到search的结果了。

添加操作:add

因为跳表是有序的,所以一定会按序添加到指定的位置上。先先find得到目标元素的prev数组,然后从最下层开始向上,除了最下面那层一定要插入,上面的层i如果(连续且随机地)需要派生这层的索引,就根据prev[i]是该节点在第i层的前置结点,在此层按照链表的方式插入这个索引就可以了。

删除操作:erase

先做一遍serach操作,确认要删除的元素存在,且构造好了prev数组,接下来从下层向上,对于每一层i,按照链表的方式判断要删除的结点在此层存在索引,就将索引删除。因为索引从下到上是连续存在的,所以删到找不到索引就一定已经删干净了,最后记得回收结点即可。

例题:LeetCode 1206. 设计跳表

class Skiplist {
private:static const int MAX_LEVEL = 8;struct Node {int val;Node** next;Node(int _val) :val(_val) {next = new Node*[MAX_LEVEL];memset(next, NULL, sizeof(Node*) * MAX_LEVEL);}} *head, **prev;void find(int target, Node** prev) {Node* p = head;for (int i = MAX_LEVEL - 1; i >= 0 ; i -- ) {while (p->next[i] && p->next[i]->val < target) p = p->next[i];prev[i] = p;}}public:Skiplist() {this->head = new Node(-1);this->prev = new Node*[MAX_LEVEL];}~Skiplist() {delete this->head;delete[] this->prev;}bool search(int target) {memset(prev, NULL, sizeof(Node*) * MAX_LEVEL);find(target, prev);auto p = prev[0]->next[0];return p && p->val == target;}void add(int num) {memset(prev, NULL, sizeof(Node*) * MAX_LEVEL);find(num, prev);auto p = new Node(num);for (int i = 0; i < MAX_LEVEL; i ++ ) {p->next[i] = prev[i]->next[i];prev[i]->next[i] = p;if (rand() % 2) break;}}bool erase(int num) {memset(prev, NULL, sizeof(Node*) * MAX_LEVEL);find(num, prev);auto p = prev[0]->next[0];if (!p || p->val != num) return false;for (int i = 0; i < MAX_LEVEL && prev[i]->next[i] == p; i ++ )prev[i]->next[i] = p->next[i];delete p;return true;}
};/*** Your Skiplist object will be instantiated and called as such:* Skiplist* obj = new Skiplist();* bool param_1 = obj->search(target);* obj->add(num);* bool param_3 = obj->erase(num);*/

相关文章:

【数据结构学习笔记】19:跳表(Skip List)

介绍 跳表是一个能在 O ( n l o g n ) O(nlogn) O(nlogn)时间完成查找、插入、删除的数据结构&#xff0c;相比于树形结构优点就是很好写&#xff08;所以也用于实现Redis ZSet&#xff09;。其核心思想就是维护一个元素有序的&#xff0c;能随机提升索引层数的链表。最下面一…...

【8】深入理解 Go 语言中的协程-从基础到高级应用

文章目录 一、引言 &#x1f31f;二、协程基础概念 &#x1f9d0;&#xff08;一&#xff09;什么是协程&#xff08;二&#xff09;协程与线程、进程的区别三、协程的创建与启动 &#x1f680;&#xff08;一&#xff09;使用 go 关键字创建协程&#xff08;二&#xff09;简单…...

深入理解 ECMAScript 2024 新特性:字符串 isWellFormed 方法

ECMAScript 2024 引入了一个新的字符串实例方法&#xff1a;String.prototype.isWellFormed。这一新增功能是为了帮助开发者更容易地验证字符串是否为有效的 Unicode 文本。本文将详细介绍这一方法的使用场景、实现原理及其在实际应用中的价值。 String.prototype.isWellFormed…...

算法分析与设计之贪心算法

文章目录 前言一、Greedy Algorithms1.1 贪心选择性质1.2 最优子结构性质1.3 正确性证明 二、典型例题2.1 Interval Scheduling间隔调度2.2 Interval Partitioning最少间教室排课2.3 Selecting Breakpoints选择加油站停靠点2.4 硬币找零2.5 Scheduling to Minimizing Lateness2…...

Centos 宝塔安装

yum install -y wget && wget -O install.sh http://download.bt.cn/install/install_6.0.sh && sh install.sh 安装成功界面 宝塔说明文档 https://www.bt.cn/admin/servers#wcu 或者可以注册宝塔账号 1 快速部署 安装docker 之后 2 需要在usr/bin下下载do…...

蓝桥与力扣刷题(709 转换成小写字母)

题目&#xff1a;给你一个字符串 s &#xff0c;将该字符串中的大写字母转换成相同的小写字母&#xff0c;返回新的字符串。 示例 1&#xff1a; 输入&#xff1a;s "Hello" 输出&#xff1a;"hello"示例 2&#xff1a; 输入&#xff1a;s "here…...

Redis的过期策略、内存淘汰机制

Redis只能存5G数据&#xff0c;可是你写了10G&#xff0c;那会删5G的数据。怎么删的&#xff1f;还有&#xff0c;你的数据已经设置了过期时间&#xff0c;但是时间到了&#xff0c;为什么内存占用率还是比较高? 一、Redis的过期策略 Redis采用的是定期删除惰性删除策略。 1…...

视觉多模态大模型---MiniMax-vl-01---以闪电般的注意力缩放基础模型

简介 MiniMax-VL-01 是与今年1月15日由上海稀宇科技有限公司&#xff08;MiniMax&#xff09;发布并开源的一款视觉多模态大模型&#xff0c;它与基础语言大模型 MiniMax-Text-01 一同构成了 MiniMax-01 系列。这款模型的设计初衷是为了应对日益增长的长上下文处理需求&#x…...

【微服务】面试 3、 服务监控 SkyWalking

微服务监控的原因 问题定位&#xff1a;在微服务架构中&#xff0c;客户端&#xff08;如 PC 端、APP 端、小程序等&#xff09;请求后台服务需经过网关再路由到各个微服务&#xff0c;服务间可能存在多链路调用。当某一微服务挂掉时&#xff0c;在复杂的调用链路中难以迅速确定…...

【案例81】NMC调用导致数据库的效率问题

问题现象 客户在使用NC系统时&#xff0c;发现系统特别卡顿。需要紧急排查。 问题分析 排查NMC发现&#xff0c;所有的线程都处于执行SQL层面&#xff0c;说明数据库当前出现了异常。查看数据库资源状态发现&#xff0c;Oracle相关进程CPU利用率达到了100%。 查看现在数据库…...

Linux_信号

信号的概念 && 知识补充 信号是进程之间事件异步通知的一种方式&#xff0c;是一种软中断。 标准信号&#xff1a;编号为1-31之间都是标准信号&#xff0c;这些都是预定义信号&#xff0c;用于通知进程发生的各种事件。实时信号&#xff1a;编号从32开始起均是实时信号…...

LeetCode100之搜索二维矩阵(46)--Java

1.问题描述 给你一个满足下述两条属性的 m x n 整数矩阵&#xff1a; 每行中的整数从左到右按非严格递增顺序排列。每行的第一个整数大于前一行的最后一个整数。 给你一个整数 target &#xff0c;如果 target 在矩阵中&#xff0c;返回 true &#xff1b;否则&#xff0c;返回…...

学员答疑:安卓分屏窗口的TouchableRegion设置流程追踪

背景&#xff1a; vip学员在群里问到了一个分屏触摸区域设置的问题&#xff0c;开始以为就是和普通Activity设置区域没啥差别,都是在InputMonitor中进行的设置&#xff0c;但是仔细研究下来其实并不是哈。本文就带大家来手把手分析一下分屏情况下的触摸区域是怎么设置的。 d…...

[cg] UE5 调试技巧

UE 中 rhi命令的提交是在render 线程&#xff0c;而graphics api 真正的执行是在rhi 线程&#xff0c; 今天想看下rhi的底层调用&#xff0c;但由于是通过task执行的&#xff0c;无法获取到render thread传入的地方&#xff0c;调试起来不太方便。 可通过开启下面的命令来调试 …...

Python Wi-Fi密码测试工具

Python Wi-Fi测试工具 相关资源文件已经打包成EXE文件&#xff0c;可双击直接运行程序&#xff0c;且文章末尾已附上相关源码&#xff0c;以供大家学习交流&#xff0c;博主主页还有更多Python相关程序案例&#xff0c;秉着开源精神的想法&#xff0c;望大家喜欢&#xff0c;点…...

Linux 创建用户

Linux 创建用户 创建用户 sudo useradd -m -s /bin/bash test - -m&#xff1a;自动创建家目录 /home/test - -s /bin/bash&#xff1a;指定默认的 shell 为 bash修改密码 # 修改密码 sudo passwd test删除用户 userdel -r zengshun - -r&#xff1a;把用户的主目录一起删…...

自建RustDesk服务器

RustDesk服务端 下面的截图是我本地的一个服务器做为演示用&#xff0c;你自行的搭建服务需要该服务器有固定的ip地址 1、通过宝塔面板快速安装 2、点击【安装】后会有一个配置信息&#xff0c;默认即可 3、点击【确认】后会自动安装等待安装完成 4、安装完成后点击【打开…...

Spring Boot Web技术栈(官网文档解读)

摘要 Spring Boot框架既支持传统的Servlet技术栈&#xff0c;也支持新兴的响应式&#xff08;Reactive&#xff09;技术栈。本篇文章将详细讲述Spring Boot 对两种技术栈的详细支持和使用。 Servlet 概述 基于Java Servlet API构建&#xff0c;它依赖于传统的阻塞I/O模型&…...

【llama_factory】qwen2_vl训练与批量推理

训练llama factory配置文件 文件&#xff1a;examples/train_lora/qwen2vl_lora_sft.yaml ### model model_name_or_path: qwen2_vl/model_72b trust_remote_code: true### method stage: sft do_train: true finetuning_type: lora lora_target: all### dataset dataset: ca…...

wpa_cli命令使用记录

wpa_cli可以用于查询当前状态、更改配置、触发事件和请求交互式用户输入。具体来说&#xff0c;它可以显示当前的认证状态、选择的安全模式、dot11和dot1x MIB等&#xff0c;并可以配置一些变量&#xff0c;如EAPOL状态机参数。此外&#xff0c;wpa_cli还可以触发重新关联和IEE…...

智慧医疗能源事业线深度画像分析(上)

引言 医疗行业作为现代社会的关键基础设施,其能源消耗与环境影响正日益受到关注。随着全球"双碳"目标的推进和可持续发展理念的深入,智慧医疗能源事业线应运而生,致力于通过创新技术与管理方案,重构医疗领域的能源使用模式。这一事业线融合了能源管理、可持续发…...

K8S认证|CKS题库+答案| 11. AppArmor

目录 11. AppArmor 免费获取并激活 CKA_v1.31_模拟系统 题目 开始操作&#xff1a; 1&#xff09;、切换集群 2&#xff09;、切换节点 3&#xff09;、切换到 apparmor 的目录 4&#xff09;、执行 apparmor 策略模块 5&#xff09;、修改 pod 文件 6&#xff09;、…...

(二)TensorRT-LLM | 模型导出(v0.20.0rc3)

0. 概述 上一节 对安装和使用有个基本介绍。根据这个 issue 的描述&#xff0c;后续 TensorRT-LLM 团队可能更专注于更新和维护 pytorch backend。但 tensorrt backend 作为先前一直开发的工作&#xff0c;其中包含了大量可以学习的地方。本文主要看看它导出模型的部分&#x…...

STM32标准库-DMA直接存储器存取

文章目录 一、DMA1.1简介1.2存储器映像1.3DMA框图1.4DMA基本结构1.5DMA请求1.6数据宽度与对齐1.7数据转运DMA1.8ADC扫描模式DMA 二、数据转运DMA2.1接线图2.2代码2.3相关API 一、DMA 1.1简介 DMA&#xff08;Direct Memory Access&#xff09;直接存储器存取 DMA可以提供外设…...

Nuxt.js 中的路由配置详解

Nuxt.js 通过其内置的路由系统简化了应用的路由配置&#xff0c;使得开发者可以轻松地管理页面导航和 URL 结构。路由配置主要涉及页面组件的组织、动态路由的设置以及路由元信息的配置。 自动路由生成 Nuxt.js 会根据 pages 目录下的文件结构自动生成路由配置。每个文件都会对…...

Ascend NPU上适配Step-Audio模型

1 概述 1.1 简述 Step-Audio 是业界首个集语音理解与生成控制一体化的产品级开源实时语音对话系统&#xff0c;支持多语言对话&#xff08;如 中文&#xff0c;英文&#xff0c;日语&#xff09;&#xff0c;语音情感&#xff08;如 开心&#xff0c;悲伤&#xff09;&#x…...

在WSL2的Ubuntu镜像中安装Docker

Docker官网链接: https://docs.docker.com/engine/install/ubuntu/ 1、运行以下命令卸载所有冲突的软件包&#xff1a; for pkg in docker.io docker-doc docker-compose docker-compose-v2 podman-docker containerd runc; do sudo apt-get remove $pkg; done2、设置Docker…...

【SSH疑难排查】轻松解决新版OpenSSH连接旧服务器的“no matching...“系列算法协商失败问题

【SSH疑难排查】轻松解决新版OpenSSH连接旧服务器的"no matching..."系列算法协商失败问题 摘要&#xff1a; 近期&#xff0c;在使用较新版本的OpenSSH客户端连接老旧SSH服务器时&#xff0c;会遇到 "no matching key exchange method found"​, "n…...

区块链技术概述

区块链技术是一种去中心化、分布式账本技术&#xff0c;通过密码学、共识机制和智能合约等核心组件&#xff0c;实现数据不可篡改、透明可追溯的系统。 一、核心技术 1. 去中心化 特点&#xff1a;数据存储在网络中的多个节点&#xff08;计算机&#xff09;&#xff0c;而非…...

ZYNQ学习记录FPGA(一)ZYNQ简介

一、知识准备 1.一些术语,缩写和概念&#xff1a; 1&#xff09;ZYNQ全称&#xff1a;ZYNQ7000 All Pgrammable SoC 2&#xff09;SoC:system on chips(片上系统)&#xff0c;对比集成电路的SoB&#xff08;system on board&#xff09; 3&#xff09;ARM&#xff1a;处理器…...