狗家电面

匿名者 发表于 2021-2-9 01:01
当时我也想到了union find，但是比如x=3 k=3 x+k = 6 x-k = 0, 假设6,0都不在数组里 但是 5,4都在 如何有 ...

不太理解你说的如果4或者5 在数组里怎么办。。
我想的是 先把所有的数存成set 然后遍历这个数组 要是x+k，x-k 在数组里就union 一下。。
有点像刷题网128longest consecutive sequence的解法 只不过128题 K=1。。
不知道我这样做时间复杂度是否好于O（N2）
我理解的 unionfind 在压缩路径下 时间复杂度应该都是 O（logN）。。。
correct me if I am wrong.

Tdvxufnek 发表于 2021-2-7 15:23
第二题也可以这样做

首先把乱序数组里面的每个 number x, 变成 [x - k, x + k] 的 range

这个不太懂，求教一下，如果 k = 2, arr = [2, 9, 12], 那么
[2, 9, 12] => [[0, 4], [7, 11], [10, 14]]，合并后是 [[0, 4], [7, 14]]
这样再扫原数组的时候岂不是会把9和12归为一组？
是不是应该变成 [x - k/2, x + k/2] 的区间？

wushi17ie 发表于 2021-02-08 23:10:22
这个不太懂，求教一下，如果 k = 2, arr = , 那么
=> , , ]，合并后是 , ]
这样再扫原数组的时候岂不是会把9和12归为一组？

海牙，大意了，不应该把value直接变成区间的，应该先拿数字扫，最后再变成区间，感谢提醒！

第二题有点儿像839

workworkhard 发表于 2021-2-9 08:59
不太理解你说的如果4或者5 在数组里怎么办。。
我想的是 先把所有的数存成set 然后遍历这个数组 要是x+ ...

这个题目的要求是“差值小于k”，并不是“等于k”。所以只查询+k, -k两个值是不够的。

能问一下第一题的输入格式吗？为啥要用分治法呢？

huali0415 发表于 2021-2-7 09:20
第二题用bucket应该可以

能详细说一下bucket的思路吗？

yiliaobailiao 发表于 2021-2-9 23:32
能详细说一下bucket的思路吗？

1，把数字全部装进buckets（hashmap即可）
2，从每个bucket出发进行dfs，每次去找左、右相邻的两个buckets看看是不是能组成一个group，并且去重
这样的话，原数组遍历一次，所有buckets遍历一次，时间和空间都是线性的

感谢LZ分享经历！

workworkhard 发表于 2021-2-9 08:59
不太理解你说的如果4或者5 在数组里怎么办。。
我想的是 先把所有的数存成set 然后遍历这个数组 要是x+ ...

嗯嗯 同另外一位小伙伴说的一样 此题要求任何绝对值差小于等于k的 都分在一个组里 所以原来的例子里 4,5也得分进去 我就不知该怎么写了