男人做爽的免费网站,做啥网站赚钱,seo全网营销,网页版传奇开服题目难度: 中等 原题链接 今天继续更新 Leetcode 的剑指 Offer#xff08;专项突击版#xff09;系列, 大家在公众号 算法精选 里回复 剑指offer2 就能看到该系列当前连载的所有文章了, 记得关注哦~ 题目描述
给你一个整数数组 nums 和两个整数 k 和 t 。请你判断是否存在 两… 题目难度: 中等 原题链接 今天继续更新 Leetcode 的剑指 Offer专项突击版系列, 大家在公众号 算法精选 里回复 剑指offer2 就能看到该系列当前连载的所有文章了, 记得关注哦~ 题目描述
给你一个整数数组 nums 和两个整数 k 和 t 。请你判断是否存在 两个不同下标 i 和 j使得 abs(nums[i] - nums[j]) t 同时又满足 abs(i - j) k 。
如果存在则返回 true不存在返回 false。
示例 1
输入nums [1,2,3,1], k 3, t 0输出true
示例 2
输入nums [1,0,1,1], k 1, t 2输出true
示例 3
输入nums [1,5,9,1,5,9], k 2, t 3输出false
提示
0 nums.length 2 * 10^4-2^31 nums[i] 2^31 - 10 k 10^40 t 2^31 - 1
题目思考
如何优化时间复杂度?
解决方案
思路
分析题目, 一个很容易想到的思路就是暴力两重循环, 外层遍历每个数字作为起点, 内层从该起点向后遍历 k 个数字, 判断是否存在差值不超过 t 的数字对不过这种做法的时间复杂度达到了 O(NK), 很容易超时, 如何优化呢?上面的暴力法是通过两重循环的方式保证下标差有效, 然后再判断差值, 我们可以换个思路, 先保证差值有效, 然后再判断下标差由于题目要求差值不超过 t, 如果我们将数字映射到一个个桶中, 然后每个桶的大小是 t1, 数字 x 对应的桶 id 就是 x/(t1), 这样就只需要遍历相邻的三个桶即可 举个例子: 对于某个数字 x, 假设其对应的桶 id 是 j, 那么只需要判断相邻的三个桶(j-1,j,j1)即可, 因为其他桶的数字与 x 的差值一定超过 t (中间至少间隔了一个桶, 即 t1) 然后每个桶存储最新映射到该桶的数字的下标, 这样就很容易判断下标差是否超过 k 了最后我们还得再次确认对应数字对的差值是否真的不超过 t, 因为相邻桶的两个数字差值可能会超过 t, 例如数字对(x, xt1)另外注意, 我们在遍历某个下标 i 时, 总是可以将对应桶的值更新为它, 因为即使之前存在另一个下标 pi 也映射到这个桶, 那么当遍历后面的某个下标 j 时 (即piij), 只可能有两种情况: pi 和 j 的下标差不超过 k: 此时 pi 和 i 的下标差更不会超过 k, 所以 pi 和 i 本身就构成了有效的数字对 (在同一个桶内, 差值总是不超过 t), 遍历 i 时就可以直接返回 truepi 和 j 的下标差超过 k: pi 和 j 不能构成有效的数字对 综合两种情况, pi 不会再被用到, 所以总是可以将桶的值更新为最新的下标 i下面代码中有详细的注释, 方便大家理解
复杂度
时间复杂度 O(N): 只需要遍历每个数字一遍空间复杂度 O(N): 额外桶映射字典, 最差情况每个数字对应独立的一个桶
代码
class Solution:def containsNearbyAlmostDuplicate(self, nums: List[int], k: int, t: int) - bool:# 将数字离散化放到对应的桶中, 每个桶的大小是t1, 数字x对应的桶id就是x/(t1)# 这样对于某个数字x, 假设其对应的桶id是j, 那么只需要判断(j-1,j,j1)三个桶即可, 因为其他桶的数字与x的差值一定超过tbuckets {}for i, x in enumerate(nums):# 求出对应桶idid x // (t 1)for nid in (id - 1, id, id 1):# 遍历相邻三个桶if nid in buckets and i - buckets[nid] k and abs(x - nums[buckets[nid]]) t:# 如果存在下标差不超过k, 且差值不超过t的数字对, 则有效# 注意这里不能省略差值判断, 因为相邻桶的两个数字差值可能会超过t, 例如数字对(x, xt1)return True# 在遍历某个下标 i 时, 总是可以将对应桶的值更新为它, 因为即使之前存在另一个下标 pi 也映射到这个桶, 那么当遍历后面的某个下标 j 时 (即piij), 只可能有两种情况:# 1. pi和j的下标差不超过k: 此时pi和i的下标差更不会超过k, 所以pi和i本身就构成了有效的数字对 (在同一个桶内, 差值总是不超过t), 遍历i时就可以直接返回true# 2. pi和j的下标差超过k: pi和j不能构成有效的数字对# 综合两种情况, pi不会再被用到, 所以总是可以将桶的值更新为最新的下标ibuckets[id] ireturn False大家可以在下面这些地方找到我~ 我的 GitHub 我的 Leetcode 我的 CSDN 我的知乎专栏 我的头条号 我的牛客网博客 我的公众号: 算法精选, 欢迎大家扫码关注~
