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

​​​【收录 Hello 算法】10.4 哈希优化策略

目录

10.4   哈希优化策略

10.4.1   线性查找:以时间换空间

10.4.2   哈希查找:以空间换时间


10.4   哈希优化策略

在算法题中,我们常通过将线性查找替换为哈希查找来降低算法的时间复杂度。我们借助一个算法题来加深理解。

Question

给定一个整数数组 nums 和一个目标元素 target ,请在数组中搜索“和”为 target 的两个元素,并返回它们的数组索引。返回任意一个解即可。

10.4.1   线性查找:以时间换空间

考虑直接遍历所有可能的组合。如图 10-9 所示,我们开启一个两层循环,在每轮中判断两个整数的和是否为 target ,若是,则返回它们的索引。

线性查找求解两数之和

图 10-9   线性查找求解两数之和

代码如下所示:

two_sum.c

/* 方法一:暴力枚举 */
int *twoSumBruteForce(int *nums, int numsSize, int target, int *returnSize) {for (int i = 0; i < numsSize; ++i) {for (int j = i + 1; j < numsSize; ++j) {if (nums[i] + nums[j] == target) {int *res = malloc(sizeof(int) * 2);res[0] = i, res[1] = j;*returnSize = 2;return res;}}}*returnSize = 0;return NULL;
}

此方法的时间复杂度为 𝑂(𝑛2) ,空间复杂度为 𝑂(1) ,在大数据量下非常耗时。

10.4.2   哈希查找:以空间换时间

考虑借助一个哈希表,键值对分别为数组元素和元素索引。循环遍历数组,每轮执行图 10-10 所示的步骤。

  1. 判断数字 target - nums[i] 是否在哈希表中,若是,则直接返回这两个元素的索引。
  2. 将键值对 nums[i] 和索引 i 添加进哈希表。

<1><2><3>

two_sum_hashtable_step3

图 10-10   辅助哈希表求解两数之和

实现代码如下所示,仅需单层循环即可:

two_sum.c

/* 哈希表 */
typedef struct {int key;int val;UT_hash_handle hh; // 基于 uthash.h 实现
} HashTable;/* 哈希表查询 */
HashTable *find(HashTable *h, int key) {HashTable *tmp;HASH_FIND_INT(h, &key, tmp);return tmp;
}/* 哈希表元素插入 */
void insert(HashTable *h, int key, int val) {HashTable *t = find(h, key);if (t == NULL) {HashTable *tmp = malloc(sizeof(HashTable));tmp->key = key, tmp->val = val;HASH_ADD_INT(h, key, tmp);} else {t->val = val;}
}/* 方法二:辅助哈希表 */
int *twoSumHashTable(int *nums, int numsSize, int target, int *returnSize) {HashTable *hashtable = NULL;for (int i = 0; i < numsSize; i++) {HashTable *t = find(hashtable, target - nums[i]);if (t != NULL) {int *res = malloc(sizeof(int) * 2);res[0] = t->val, res[1] = i;*returnSize = 2;return res;}insert(hashtable, nums[i], i);}*returnSize = 0;return NULL;
}

此方法通过哈希查找将时间复杂度从 𝑂(𝑛2) 降至 𝑂(𝑛) ,大幅提升运行效率。

由于需要维护一个额外的哈希表,因此空间复杂度为 𝑂(𝑛) 。尽管如此,该方法的整体时空效率更为均衡,因此它是本题的最优解法

相关文章:

​​​【收录 Hello 算法】10.4 哈希优化策略

目录 10.4 哈希优化策略 10.4.1 线性查找&#xff1a;以时间换空间 10.4.2 哈希查找&#xff1a;以空间换时间 10.4 哈希优化策略 在算法题中&#xff0c;我们常通过将线性查找替换为哈希查找来降低算法的时间复杂度。我们借助一个算法题来加深理解。 Question 给…...

浅析部署架构中的GZone、RZone和CZone

在现代软件开发中&#xff0c;理解和应用各种技术概念是成功的重要因素。本文将详细介绍GZone、RZone和CZone三个概念&#xff0c;解释它们的定义、特点、功能及应用场景&#xff0c;并通过实际案例帮助读者更好地理解这些概念。 一、GZone 1.1 定义 GZone是指“Global Zone…...

【全开源】分类记账小程序系统源码(ThinkPHP+FastAdmin+UniApp)

基于ThinkPHPFastAdminUniAppvk-uView-uiVue3.0开发的一款支持多人协作的记账本小程序&#xff0c;可用于家庭&#xff0c;团队&#xff0c;组织以及个人的日常收支情况记录&#xff0c;支持周月年度统计。 &#xff1a;智能管理您的财务生活 一、引言&#xff1a;财务智能化…...

Android NDK系列(四)NDK的编译

Native工程一般会用到NDK&#xff0c;一般开发者使用的NDK是官方提供的&#xff0c;直接下载即可使用。在工作过程中一般很少要定义NDK&#xff0c;不过对于想了解NDK是怎么生成的&#xff0c;可以继续往下阅读。 Google提供了编译NDK的说明文档&#xff0c;地址为NDK编译&…...

Jenkins--从入门到入土

Jenkins–从入门到入土 文章目录 Jenkins--从入门到入土〇、概念提要--什么是CI/DI&#xff1f;1、CI&#xff08;Continuous Integration&#xff0c;持续集成&#xff09;2、DI&#xff08;DevOps Integration&#xff0c;DevOps 集成&#xff09;3、解决的问题 一、Jenkins安…...

文心一言 VS 讯飞星火 VS chatgpt (267)-- 算法导论20.2 2题

二、写出 PROTO-vEB-DELETE 的伪代码。通过扫描簇内的相关位&#xff0c;来更新相应的 summary 位。并且你实现的伪代码的最坏情况运行时间是多少&#xff1f;如果要写代码&#xff0c;请用go语言。 文心一言&#xff1a; 首先&#xff0c;让我们回顾一下vEB&#xff08;Van …...

C 语言设计模式(结构型)

文章目录 代理模式场景示例 门面模式场景示例 桥接模式场景示例 适配器模式场景示例 外观模式场景示例 享元模式场景示例 装饰器模式场景示例 组合模式场景示例 代理模式 C语言中&#xff0c;代理模式通常用于实现对象的间接访问。代理模式是一种结构型设计模式&#xff0c;它…...

【云原生--K8S】K8S python接口研究

文章目录 前言一、搭建ubuntu运行环境1.运行ubuntu容器2.拷贝kubeconfig文件二、python程序获取k8s信息1.获取node信息2.获取svc信息3.常用kubernetes API总结前言 在前面的文章中我们都是通过kubectl命令行来访问操作K8S,但是在实际应用中可能需要提供更方便操作的图形化界面…...

5.26作业

服务器 2 3 #define BUFSIZE 10244 #define login_msg_len 205 6 typedef struct Node{7 char name[login_msg_len];8 struct sockaddr_in addr;9 struct Node *next;10 }Node;11 12 typedef struct Msgtype{13 char type;14 char username[login_msg_len]…...

链接库文件体积优化工具篇:bloaty

笔者之前参与过一个嵌入式智能手表项目&#xff0c;曾经碰到过这样一个问题&#xff1a;手表的flash大小只有2M&#xff0c;这意味着只能在上面烧录2M大小的代码。随着开发不断进行&#xff0c;代码越写越多&#xff0c;编译出来的bin也越来越大。最后bin大小超过了2M, 就没法烧…...

使用pyqt绘制一个爱心!

使用pyqt绘制一个爱心&#xff01; 介绍效果代码 介绍 使用pyqt绘制一个爱心&#xff01; 效果 代码 import sys from PyQt5.QtWidgets import QApplication, QMainWindow, QWidget from PyQt5.QtGui import QPainter, QPen, QBrush, QColor from PyQt5.QtCore import Qt, Q…...

关于 Transformer 的11个常见面试题

Transformer 是如何工作的&#xff1f; Transformer 是一种深度学习算法&#xff0c;特别适用于自然语言处理&#xff08;NLP&#xff09;任务&#xff0c;如语言翻译、语言生成和语言理解。它们能够处理长度可变的输入序列并捕捉长距离依赖关系&#xff0c;使其在理解和处理自…...

OS多核多线程锁记录笔记

自旋锁作用 自旋锁的是为了保护两个核上的公共资源&#xff0c;也就是全局变量&#xff0c;只有在一方也就是一个核抢到了自选锁&#xff0c;才能对公共资源进行操作修改&#xff0c;当然还有其他形似的锁如互斥锁&#xff0c;这里不比较两者的区别&#xff0c;以前没有深入的去…...

nginx做TCP代理

要实现TCP代理&#xff0c;可以使用Nginx的stream模块。stream模块允许Nginx作为一个转发代理来处理TCP流量&#xff0c;包括TCP代理、负载均衡和SSL终止等功能。 以下是配置Nginx实现TCP代理的基本步骤&#xff1a; 在Nginx配置文件中添加stream块&#xff0c;并在该块中配置…...

python 异常处理 try

异常 我们常见的代码错误后 会出现此类异常 SyntaxError&#xff1a;语法错误 AttributeError&#xff1a;属性错误 IndexError&#xff1a;索引错误 TypeError&#xff1a;类型错误 NameError&#xff1a;变量名不存在错误 KeyError&#xff1a;映射中不存在的关键字&#xf…...

月入10万+管道收益,揭秘旅游卡运营的5个阶段!

网上的项目众多&#xff0c;只要用心&#xff0c;便能发现不少商机。在互联网上运营&#xff0c;关键在于理解项目的底层逻辑。今天&#xff0c;我们来揭秘旅游卡项目&#xff0c;如何做到月入10万。 1、先赚成本 开始项目时&#xff0c;首要任务是回本。不要急于求成&#x…...

android_binder源码分析之_binder驱动使用服务

一&#xff0c;binder驱动源码分析&#xff0c;使用服务过程 uint32_t svcmgr_lookup(struct binder_state *bs, uint32_t target, const char *name) {uint32_t handle;unsigned iodata[512/4];struct binder_io msg, reply;bio_init(&msg, iodata, sizeof(iodata), 4);b…...

【波点音乐看广告】

import uiautomator2 as u2 import time from datetime import datetime import xml.etree.ElementTree as ET import re import os 连接设备 d u2.connect() os.system(‘adb shell chmod 775 /data/local/tmp/atx-agent’) os.system(‘adb shell /data/local/tmp/atx-age…...

[SWPUCTF 2021 新生赛]pop

常见的魔术方法 魔术方法__construct() 类的构造函数&#xff0c;在对象实例化时调用 __destruct() 类的析构函数&#xff0c;在对象被销毁时被调用 __call() 在对象中调用一个不可访问的对象时被调用&#xff0c;比如一个对象被调用时&#xff0c;里面没有程序想调用的属性 …...

【DevOps】Jenkins + Dockerfile自动部署Maven(SpringBoot)项目

环境 docker_host192.168.0.1jenkins_host192.168.0.2 jenkins_host构建完成后把jar发布到docker_host&#xff0c;再通过dockerfile自动构建镜像&#xff0c;运行镜像 1 Jenkins安装 AWS EC2安装Jenkins&#xff1a;AWS EC2 JDK11 Jenkins-CSDN博客 AWS EC2上Docker安装…...

后进先出(LIFO)详解

LIFO 是 Last In, First Out 的缩写&#xff0c;中文译为后进先出。这是一种数据结构的工作原则&#xff0c;类似于一摞盘子或一叠书本&#xff1a; 最后放进去的元素最先出来 -想象往筒状容器里放盘子&#xff1a; &#xff08;1&#xff09;你放进的最后一个盘子&#xff08…...

PHP和Node.js哪个更爽?

先说结论&#xff0c;rust完胜。 php&#xff1a;laravel&#xff0c;swoole&#xff0c;webman&#xff0c;最开始在苏宁的时候写了几年php&#xff0c;当时觉得php真的是世界上最好的语言&#xff0c;因为当初活在舒适圈里&#xff0c;不愿意跳出来&#xff0c;就好比当初活在…...

基于uniapp+WebSocket实现聊天对话、消息监听、消息推送、聊天室等功能,多端兼容

基于 ​UniApp + WebSocket​实现多端兼容的实时通讯系统,涵盖WebSocket连接建立、消息收发机制、多端兼容性配置、消息实时监听等功能,适配​微信小程序、H5、Android、iOS等终端 目录 技术选型分析WebSocket协议优势UniApp跨平台特性WebSocket 基础实现连接管理消息收发连接…...

渗透实战PortSwigger靶场-XSS Lab 14:大多数标签和属性被阻止

<script>标签被拦截 我们需要把全部可用的 tag 和 event 进行暴力破解 XSS cheat sheet&#xff1a; https://portswigger.net/web-security/cross-site-scripting/cheat-sheet 通过爆破发现body可以用 再把全部 events 放进去爆破 这些 event 全部可用 <body onres…...

Java多线程实现之Callable接口深度解析

Java多线程实现之Callable接口深度解析 一、Callable接口概述1.1 接口定义1.2 与Runnable接口的对比1.3 Future接口与FutureTask类 二、Callable接口的基本使用方法2.1 传统方式实现Callable接口2.2 使用Lambda表达式简化Callable实现2.3 使用FutureTask类执行Callable任务 三、…...

【android bluetooth 框架分析 04】【bt-framework 层详解 1】【BluetoothProperties介绍】

1. BluetoothProperties介绍 libsysprop/srcs/android/sysprop/BluetoothProperties.sysprop BluetoothProperties.sysprop 是 Android AOSP 中的一种 系统属性定义文件&#xff08;System Property Definition File&#xff09;&#xff0c;用于声明和管理 Bluetooth 模块相…...

Module Federation 和 Native Federation 的比较

前言 Module Federation 是 Webpack 5 引入的微前端架构方案&#xff0c;允许不同独立构建的应用在运行时动态共享模块。 Native Federation 是 Angular 官方基于 Module Federation 理念实现的专为 Angular 优化的微前端方案。 概念解析 Module Federation (模块联邦) Modul…...

Spring Boot+Neo4j知识图谱实战:3步搭建智能关系网络!

一、引言 在数据驱动的背景下&#xff0c;知识图谱凭借其高效的信息组织能力&#xff0c;正逐步成为各行业应用的关键技术。本文聚焦 Spring Boot与Neo4j图数据库的技术结合&#xff0c;探讨知识图谱开发的实现细节&#xff0c;帮助读者掌握该技术栈在实际项目中的落地方法。 …...

自然语言处理——Transformer

自然语言处理——Transformer 自注意力机制多头注意力机制Transformer 虽然循环神经网络可以对具有序列特性的数据非常有效&#xff0c;它能挖掘数据中的时序信息以及语义信息&#xff0c;但是它有一个很大的缺陷——很难并行化。 我们可以考虑用CNN来替代RNN&#xff0c;但是…...

DeepSeek 技术赋能无人农场协同作业:用 AI 重构农田管理 “神经网”

目录 一、引言二、DeepSeek 技术大揭秘2.1 核心架构解析2.2 关键技术剖析 三、智能农业无人农场协同作业现状3.1 发展现状概述3.2 协同作业模式介绍 四、DeepSeek 的 “农场奇妙游”4.1 数据处理与分析4.2 作物生长监测与预测4.3 病虫害防治4.4 农机协同作业调度 五、实际案例大…...