力扣题解(设计跳表)

1206.设计跳表

已解答

不使用任何库函数,设计一个 跳表 。

跳表 是在 O(log(n)) 时间内完成增加、删除、搜索操作的数据结构。跳表相比于树堆与红黑树,其功能与性能相当,并且跳表的代码长度相较下更短,其设计思想与链表相似。

例如,一个跳表包含 [30, 40, 50, 60, 70, 90] ,然后增加 8045 到跳表中,以下图的方式操作:

跳表中有很多层,每一层是一个短的链表。在第一层的作用下,增加、删除和搜索操作的时间复杂度不超过 O(n)。跳表的每一个操作的平均时间复杂度是 O(log(n)),空间复杂度是 O(n)

了解更多 : 跳表 - OI Wiki

在本题中,你的设计应该要包含这些函数:

  • bool search(int target) : 返回target是否存在于跳表中。
  • void add(int num): 插入一个元素到跳表。
  • bool erase(int num): 在跳表中删除一个值,如果 num 不存在,直接返回false. 如果存在多个 num ,删除其中任意一个即可。

注意,跳表中可能存在多个相同的值,你的代码需要处理这种情况。

本题主要难点在于理解调表的构造和查找元素的做法。首先,调表的优势在于可以一下子跳过很多元素,所以叫跳表,而能一下跳过很多元素的原因是跳表中存在多层的元素,如果高层可以通过,则高层之间的底层可以忽略,实现了跳过多个元素。

越往上层数越高。

此时从-3所在节点开始走,若比10大,则可以跳过和低层的2,6比较,实现了跳跃。

跳表实现最复杂的地方是找数值是num的节点对应的所有前一个节点(即每层的前一个节点),实现方法是从最高层开始查找,当节点的值大于num或者节点是不存在时,则本层的前一个前一个节点找到,在去低一层找,之所以可以去低一层找,是因为低一层中存放的节点值一定是在高一层的节点的值中间,而与num的大小不能确定,因此需要去进一步查找。

	vector<node*>findprevnode(int num)
	{
		int level = _root->_next.size();
		vector<node*>pre(level);
		level--;
		node* cur = _root;
		while (level >= 0)
		{
			if (cur->_next[level] && cur->_next[level]->_val < num)
			{
				cur = cur->_next[level];
			}
			else if (cur->_next[level] == nullptr || cur->_next[level]->_val >= num)
			{
				pre[level--] = cur;
			}
		}
		return  pre;
	}

对于插入和删除,搜索,都是复用了这个函数,找到对应前一个节点位置,然后进行插入,删除操作即可。对于搜索,只需要从返回的数组的下标为0的节点判断即可,因为该节点所指的下一个节点一定是数组所有节点所指的下一个节点的最小值,如果这个节点存放的值都不对,则必定找不到所需的节点。

class Skiplist {
public:

	struct skiplistnode
	{
		int _val;
		vector<skiplistnode*>_next;

		skiplistnode()
			:_val(-1)
		{

		}

		skiplistnode(int num, int n)
		{
			_val = num;
			_next.resize(n, nullptr);
		}
	};

	typedef skiplistnode node;
	node* _root;

	Skiplist() {
		srand((unsigned)time(nullptr));
		_root = new node();
	}




	vector<node*>findprevnode(int num)
	{
		int level = _root->_next.size();
		vector<node*>pre(level);
		level--;
		node* cur = _root;
		while (level >= 0)
		{
			if (cur->_next[level] && cur->_next[level]->_val < num)
			{
				cur = cur->_next[level];
			}
			else if (cur->_next[level] == nullptr || cur->_next[level]->_val >= num)
			{
				pre[level--] = cur;
			}
		}
		return  pre;
	}

    
	bool search(int target) {
       vector<node*>prevnode = findprevnode(target);
		if (prevnode[0]->_next[0] == nullptr || prevnode[0]->_next[0]->_val != target)
		{
			return false;
		}
        else
          {
            return true;
          }
	}



	int creatrand()
	{

		int level = 1;
		double p = 0.5;
		
		int it = rand();
		int itt = RAND_MAX * p;
	//	cout << it << " " << itt << endl;
		while (level <= 32 && rand() < RAND_MAX * p)
		{   
			level++;
		}
		return level;


	}
	void add(int num) {
		vector<node*>prevnode = findprevnode(num);
		int n = creatrand();
		if (n > _root->_next.size())
		{
			_root->_next.resize(n);
			prevnode.resize(n,_root);
		}
		node* cur = new node(num, n);

		for (int i = 0; i < n; i++)
		{
			cur->_next[i] = prevnode[i]->_next[i];
			prevnode[i]->_next[i] = cur;
		}

	}

	bool erase(int num) {
		vector<node*>prevnode = findprevnode(num);
		if (prevnode[0]->_next[0] == nullptr || prevnode[0]->_next[0]->_val != num)
		{
			return false;
		}
		else
		{
			node* cur = prevnode[0]->_next[0];
			for (int i = 0; i < cur->_next.size(); i++)
			{
				prevnode[i]->_next[i] = cur->_next[i];
			}
			delete cur;
			return true;
		}
	}
};

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/791415.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

Linux文件编程应用

目录 一、实现cp命令 二、修改程序的配置文件 三、写一个整数/结构体到文件 1.写一个整数到文件 2.写一个结构体到文件 四、写结构体数组到文件 我们学习了文件编程的常用指令以及了解文件编程的基本步骤后&#xff0c;试着来写一些程序实现某些功能。&#xff08;没有学…

oracle哪些后台进程不能杀?

oracle 有很多的后台进程&#xff0c;在遇到特殊情况的时候如锁表&#xff0c;如果等待的是一个后台进程&#xff0c;那这时就需要考量是不是能杀掉这个后台进程&#xff1f;杀掉这个后台进程会不会引起实例崩溃&#xff1f;本着实践出真知&#xff0c;本文针对oracle 11g&…

昇思25天学习打卡营第23天 | Pix2Pix实现图像转换

内容介绍&#xff1a; Pix2Pix是基于条件生成对抗网络&#xff08;cGAN, Condition Generative Adversarial Networks &#xff09;实现的一种深度学习图像转换模型&#xff0c;该模型是由Phillip Isola等作者在2017年CVPR上提出的&#xff0c;可以实现语义/标签到真实图片、灰…

二分法求函数的零点 信友队

题目ID&#xff1a;15713 必做题 100分 时间限制: 1000ms 空间限制: 65536kB 题目描述 有函数&#xff1a;f(x) 已知f(1.5) > 0&#xff0c;f(2.4) < 0 且方程 f(x) 0 在区间 [1.5,2.4] 有且只有一个根&#xff0c;请用二分法求出该根。 输入格式 &#xff08;无…

政安晨:【Keras机器学习示例演绎】(五十三)—— 使用 TensorFlow 决策森林进行分类

目录 简介 设置 准备数据 定义数据集元数据 配置超参数 实施培训和评估程序 实验 1&#xff1a;使用原始特征的决策森林 检查模型 实验 2&#xff1a;目标编码决策森林 创建模型输入 使用目标编码实现特征编码 使用预处理器创建梯度提升树模型 训练和评估模型 实验…

从零开始学习嵌入式----C语言框架梳理与后期规划

目录 一、环境搭建. 二、见解 三、C语言框架梳理 四、嵌入式学习规划流程图&#xff08;学习顺序可能有变&#xff09; 一、环境搭建. C语言是一门编程语言&#xff0c;在学习的时候要准备好环境。我个人比较喜欢用VS,具体怎么安装请百度。学习C语言的时候&#xff0c;切忌…

Spring中如何操作Redis

Spring毕竟是Java中的一个主流框架&#xff0c;如何在这个框架中使用Redis呢&#xff1f; 创建项目并引入相关依赖 然后进行创建。 至此就将Redis的相关依赖引入进来了。 编写Redis配置 将application.properties修改成application.yml 然后编写如下配置&#xff1a; spr…

各向异性含水层中地下水三维流基本微分方程的推导

各向异性含水层中地下水三维流基本微分方程的推导 参考文献&#xff1a; [1] 刘欣怡,付小莉.论连续性方程的推导及几种形式转换的方法[J].力学与实践,2023,45(02):469-474. 文章链接 水均衡的基本思想&#xff1a; ∑ 流 入 − ∑ 流 出 Δ V \sum 流入-\sum 流出\Delta V ∑…

ArduPilot开源飞控之AP_Mount_Siyi

ArduPilot开源飞控之AP_Mount_Siyi 1. 源由2. 框架设计2.1 类和继承2.2 公共方法2.3 保护方法2.4 私有成员和方法2.5 解析状态2.6 重要成员变量 3. 重要方法3.1 AP_Mount_Siyi::init3.2 AP_Mount_Siyi::update3.3 AP_Mount_Siyi::read_incoming_packets3.4 AP_Mount_Siyi::proc…

LabVIEW实现LED显示屏视觉检测

为了满足LED显示屏在生产过程中的严格质量检测需求&#xff0c;引入自动化检测系统是十分必要的。传统人工检测方式存在检测强度高、效率低、准确性差等问题&#xff0c;自动化检测系统则能显著提高检测效率和准确性。视觉检测系统的构建主要包含硬件和软件两个部分。 视觉系统…

深度学习论文: LLaMA: Open and Efficient Foundation Language Models

深度学习论文: LLaMA: Open and Efficient Foundation Language Models LLaMA: Open and Efficient Foundation Language Models PDF:https://arxiv.org/pdf/2302.13971.pdf PyTorch: https://github.com/shanglianlm0525/PyTorch-Networks 1 概述 本文介绍了LLaMA&#xff0…

一二三应用开发平台应用开发示例(7)——文档功能实现示例

概述 在完成文件夹配置工作后&#xff0c;接下来配置文档管理系统最核心的管理对象“文档”。 依旧是使用平台低代码配置工作来配置&#xff0c;配置流程跟文件夹的配置是相同的&#xff0c;以下简要说明&#xff0c;重点是新涉及到的功能或注意点。 创建实体 配置模型属性 …

【Dison夏令营 Day 15】 Python 鸡蛋捕手

在本次课程中&#xff0c;我们使用 Python 创建了经典的 "抓蛋 "游戏。在这个游戏中&#xff0c;每抓到一个鸡蛋就能赢得 10 分&#xff0c;而每掉落一个鸡蛋就会损失一条命。 小时候&#xff0c;我们都玩过 "抓鸡蛋 "游戏。我们使用海龟软件包在 Python …

【linux】阿里云centos配置邮件服务

目录 1.安装mailx服务 2./etc/mail.rc 配置增加 3.QQ邮箱开启smtp服务&#xff0c;获取授权码 4.端口设置&#xff1a;Linux 防火墙开放端口-CSDN博客 5.测试 1.安装mailx服务 yum -y install mailx 2./etc/mail.rc 配置增加 #邮件发送人 set from924066173qq.com #阿里…

windows USB 设备驱动开发-USB电源管理(一)

符合通用串行总线 (USB) 规范的 USB 设备的电源管理功能具有一组丰富而复杂的电源管理功能。 请务必了解这些功能如何与 Windows 驱动程序模型 (WDM) 交互&#xff0c;特别是 Microsoft Windows 如何调整标准 USB 功能以支持系统唤醒体系结构。 基于内核模式驱动程序框架的 US…

android13 rom 开发总纲说明

1. 这里是文章总纲&#xff0c;可以在这里快速找到需要的文章。 2. 文章一般是基于标准的android13&#xff0c;有一些文章可能会涉及到具体平台&#xff0c;例如全志&#xff0c;瑞芯微等一些平台。 3.系统应用 3.1系统应用Launcher3桌面相关&#xff1a; 3.2系统应用设置S…

NLP入门——词袋语言模型的搭建、训练与预测

卷积语言模型实际上是取了句子最后ctx_len个词作为上下文输入模型来预测之后的分词。但更好的选择是我们做一个词袋&#xff0c;将所有分词装在词袋中作为上下文&#xff0c;这样预测的分词不只根据最后ctx_len个分词&#xff0c;而是整个词袋中的所有分词。 例如我们的序列是&…

绝对值不等式运用(C++)

货仓选址 用数学公式表达题意&#xff0c;假设有位置a1~an,假设选址在x位置处&#xff0c;则有&#xff1a; 如何让这个最小&#xff0c;我们把两个式子整合一下&#xff0c;利用绝对值不等式&#xff1a; 我们知道&#xff1a; 如下图所示&#xff1a;到A&#xff0c;B两点&…

【深度学习入门篇 ②】Pytorch完成线性回归!

&#x1f34a;嗨&#xff0c;大家好&#xff0c;我是小森( &#xfe61;ˆoˆ&#xfe61; )&#xff01; 易编橙终身成长社群创始团队嘉宾&#xff0c;橙似锦计划领衔成员、阿里云专家博主、腾讯云内容共创官、CSDN人工智能领域优质创作者 。 易编橙&#xff1a;一个帮助编程小…

简单状压dp(以力扣464为例)

目录 1.状态压缩dp是啥&#xff1f; 2.题目分析 3.解题思路 4.算法分析 5.代码分析 6.代码一览 7.结语 1.状态压缩dp是啥&#xff1f; 顾名思义&#xff0c;状态压缩dp就是将原本会超出内存限制的存储改用更加有效的存储方式。简而言之&#xff0c;就是压缩dp的空间。 …