《剑指 Offer》专项突破版 - 面试题 57 : 值和下标之差都在给定的范围内(详解 C++ 实现的两种方法)

本文主要是介绍《剑指 Offer》专项突破版 - 面试题 57 : 值和下标之差都在给定的范围内(详解 C++ 实现的两种方法),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

目录

前言

一、时间复杂度为 O(nlogk) 的解法

二、时间复杂度为 O(n) 的解法


 


前言

题目链接:LCR 057. 存在重复元素 III - 力扣(LeetCode)

题目

给定一个整数数组 nums 和两个正数 k、t,请判断是否存在两个不同的下标 i 和 j 满足 i 和 j 之差的绝对值不大于给定的 k,并且两个数值 nums[i] 和 nums[j] 的差的绝对值不大于给定的 t。

例如,如果输入数组 { 1, 2, 3, 1 },k 为 3,t 为 0,由于下标 0 和下标 3 对应的数字之差的绝对值为 0,因此返回 true。如果输入数组 { 1, 5, 9, 1, 5, 9 },k 为 2,t 为 3,由于不存在两个下标之差小于或等于 2 且它们差的绝对值小于或等于 3 的数字,因此此时应该返回 false。

分析

首先考虑最直观的解法。可以逐一扫描数组中的每个数字。对于每个数字 nums[i],需要逐一检查在它前面的 k 个数字是否存在从 nums[i] - t 到 nums[i] + t 的范围内的数字。如果存在,则返回 true。这种思路很容易用两个嵌套的循环实现。

由于数组中的每个数字都要和 k 个数字进行比较,如果数组的长度为 n,那么这种解法的时间复杂度是 O(nk)。接下来尝试优化时间复杂度。


一、时间复杂度为 O(nlogk) 的解法

遍历数组 nums,对于数组中的每个数字 nums[i],我们在有序集合 set 中查找第一个大于或等于 nums[i] - t 的数字,如果数字存在,并且该数字小于或等于 nums[i] + t,说明找到了一对符合条件的数字,返回 true。否则,我们将 nums[i] 插入有序集合中,并且如果有序集合的大小超过 k,我们需要将最早插入有序集合的数字删除

class Solution {
public:bool containsNearbyAlmostDuplicate(vector<int>& nums, int k, int t) {set<long> s;for (int i = 0; i < nums.size(); ++i){set<long>::iterator it = s.lower_bound((long)nums[i] - t);if (it != s.end() && *it <= (long)nums[i] + t)return true;
​s.insert(nums[i]);if (i >= k)s.erase(nums[i - k]);}return false;}
};

该算法的空间复杂度是 O(k),时间复杂度是 O(nlogk)


二、时间复杂度为 O(n) 的解法

由于这个题目关心的是差的绝对值小于或等于 t 的数字,因此可以将数字放入若干大小为 t + 1 的桶中。例如,将从 0 到 t 的数字放入编号为 0 的桶中,从 t + 1 到 2t + 1 的数字放入编号为 1 的桶中,其他数字以此类推。这样做的好处是如果两个数字被放入同一个桶中,那么它们的差的绝对值一定小于或等于 t

注意:-t - 1 到 -1 的数字放入编号为 -1 的桶中

还是逐一扫描数组中的数字。如果当前扫描到数字 num,那么它将放入编号为 id 的桶中。如果这个桶中之前已经有数字,那么就找到两个差的绝对值小于或等于 t 的数字。

这段话表明每个桶中只能装一个数字,因此可以用一个哈希表来表示若干大小为 t + 1 的桶,哈希表的键表示桶的编号,值表示装在桶中的一个数字

如果桶中之前没有数字,则再判断编号为 id - 1 和 id + 1 的这两个相邻的桶中是否存在与 num 的差的绝对值小于或等于 t 的数字。因为其他桶中的数字与 num 的差的绝对值一定大于 t,所以不需要判断其他的桶中是否有符合条件的数字

class Solution {
public:bool containsNearbyAlmostDuplicate(vector<int>& nums, int k, int t) {unordered_map<int, int> buckets;long bucketSize = (long)t + 1;for (int i = 0; i < nums.size(); ++i){int num = nums[i];int id = getBucketID(num, bucketSize);if (buckets.count(id))return true;if (buckets.count(id - 1) && (long)buckets[id - 1] + t >= num)return true;if (buckets.count(id + 1) && (long)buckets[id + 1] - t <= num)return true;buckets[id] = num;if (i >= k)buckets.erase(getBucketID(nums[i - k], bucketSize));}return false;}
private:int getBucketID(int num, long bucketSize) {if (num >= 0)return num / bucketSize;elsereturn (num + 1) / bucketSize - 1;}
};

该算法的空间复杂度是 O(k),时间复杂度是 O(n)

这篇关于《剑指 Offer》专项突破版 - 面试题 57 : 值和下标之差都在给定的范围内(详解 C++ 实现的两种方法)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/742853

相关文章

QT移植到RK3568开发板的方法步骤

《QT移植到RK3568开发板的方法步骤》本文主要介绍了QT移植到RK3568开发板的方法步骤,文中通过图文示例介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一... 目录前言一、获取SDK1. 安装依赖2. 获取SDK资源包3. SDK工程目录介绍4. 获取补丁包二

Java反转字符串的五种方法总结

《Java反转字符串的五种方法总结》:本文主要介绍五种在Java中反转字符串的方法,包括使用StringBuilder的reverse()方法、字符数组、自定义StringBuilder方法、直接... 目录前言方法一:使用StringBuilder的reverse()方法方法二:使用字符数组方法三:使用自

Qt把文件夹从A移动到B的实现示例

《Qt把文件夹从A移动到B的实现示例》本文主要介绍了Qt把文件夹从A移动到B的实现示例,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学... 目录如何移动一个文件? 如何移动文件夹(包含里面的全部内容):如何删除文件夹:QT 文件复制,移动(

Flask 验证码自动生成的实现示例

《Flask验证码自动生成的实现示例》本文主要介绍了Flask验证码自动生成的实现示例,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习... 目录生成图片以及结果处理验证码蓝图html页面展示想必验证码大家都有所了解,但是可以自己定义图片验证码

VSCode配置Anaconda Python环境的实现

《VSCode配置AnacondaPython环境的实现》VisualStudioCode中可以使用Anaconda环境进行Python开发,本文主要介绍了VSCode配置AnacondaPytho... 目录前言一、安装 Visual Studio Code 和 Anaconda二、创建或激活 conda

使用mvn deploy命令上传jar包的实现

《使用mvndeploy命令上传jar包的实现》本文介绍了使用mvndeploy:deploy-file命令将本地仓库中的JAR包重新发布到Maven私服,文中通过示例代码介绍的非常详细,对大家的学... 目录一、背景二、环境三、配置nexus上传账号四、执行deploy命令上传包1. 首先需要把本地仓中要

JAVA封装多线程实现的方式及原理

《JAVA封装多线程实现的方式及原理》:本文主要介绍Java中封装多线程的原理和常见方式,通过封装可以简化多线程的使用,提高安全性,并增强代码的可维护性和可扩展性,需要的朋友可以参考下... 目录前言一、封装的目标二、常见的封装方式及原理总结前言在 Java 中,封装多线程的原理主要围绕着将多线程相关的操

SpringIoC与SpringDI详解

《SpringIoC与SpringDI详解》本文介绍了Spring框架中的IoC(控制反转)和DI(依赖注入)概念,以及如何在Spring中使用这些概念来管理对象和依赖关系,感兴趣的朋友一起看看吧... 目录一、IoC与DI1.1 IoC1.2 DI二、IoC与DI的使用三、IoC详解3.1 Bean的存储

MySQL中实现多表查询的操作方法(配sql+实操图+案例巩固 通俗易懂版)

《MySQL中实现多表查询的操作方法(配sql+实操图+案例巩固通俗易懂版)》本文主要讲解了MySQL中的多表查询,包括子查询、笛卡尔积、自连接、多表查询的实现方法以及多列子查询等,通过实际例子和操... 目录复合查询1. 回顾查询基本操作group by 分组having1. 显示部门号为10的部门名,员

Spring Cloud之注册中心Nacos的使用详解

《SpringCloud之注册中心Nacos的使用详解》本文介绍SpringCloudAlibaba中的Nacos组件,对比了Nacos与Eureka的区别,展示了如何在项目中引入SpringClo... 目录Naacos服务注册/服务发现引⼊Spring Cloud Alibaba依赖引入Naco编程s依