狗家电面

匿名者 发表于 2021-2-10 06:33
如果找左右两个bucket，是否得对bucket进行排序，或者用priority quene呢，这样的话又变成nlogn的了

bucket的顺序是固定的。首先找到min和max的值。这样的话，buckets就是[min, min + k), [min + k, min + 2k), ..., [max - k, max + 1)。我们只关心落到每个bucket里面的数字的范围，而不关心同一个bucket里面的相对顺序。buckets[j] can be merged with buckets[j + 1] if max(buckets[j]) + k >= min(buckets[j + 1]).

workworkhard 发表于 2021-2-10 06:38
明白了！感谢大神 是我理解错题意了

不敢当不敢当。。

yiliaobailiao 发表于 2021-2-10 09:06
不敢当不敢当。。

不过我后来又想 能不能merge K次
比如 x,x+1,x-1 union
x,x+2,x-2 merge
...
以此类推
这样如果K不是很大的时候  时间复杂度应该是优于O（N2）的？

gyzdmgqy 发表于 2021-2-10 06:16
这部分还是不是太懂，能否举例展开说说"应该先拿数字扫，最后再变成区间。。。"非常感谢哈

原来你是送米王 你说了算

1. 
   
2. def find_group(numbers, k):
   
3.     idx = 0
   
4.     number_index = dict()
   
5.     sorted_numbers = sorted(numbers)
   
6. 
   
7.     for i, number in enumerate(sorted_numbers):
   
8.         if i != 0 and number - sorted_numbers[i - 1] > k:
   
9.             idx += 1
   
10.         number_index[number] = idx
    
11. 
    
12.     ans = [[] for i in range(idx + 1)]
    
13.     for number in numbers:
    
14.         ans[number_index[number]].append(number)
    
15.     return ans
    

复制代码

第二题UnionFind可以吧，先排序，扫一遍，如果相邻差别 <=k, 就把这两个 union 起来

你好，能说一下题号吗？ 积分太低了，看不到

楼下有小伙伴要求提供题号，实在抱歉这两题都没找到相似的原题所以无法贴题号，抱歉哈

匿名者 发表于 2021-2-10 06:26
timeline 就是每两个月投3个狗家的职位 投了1年了 基本已经放弃了 压根没指望狗家回复 结果recruiter就找 ...

加油！！！谢谢楼主分享

感谢分享，楼里大神真多。总结下想法就是：应用排序，首先按照从小到大的顺序排序O(nlogn), 然后相邻的如果差值小于k 那就联合,线性。联合查找用路径压缩和秩排序的uf类就行。最后查询一次即可。时间复杂度O(nlogn)。如果想要继续降低复杂度，主要就是排序带来的O(nlogn)那么可以采用桶排序，一次遍历找到最小值和最大值，然后用宽度k来分割形成桶。数组依次遍历划分到对应的桶。桶内肯定属于一个group 每个桶与相邻的桶（或者右侧的桶）进行试图合并，做完也是线性复杂度。最终事件复杂度O(N)

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

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

不行呀 [2,5,8] k = 2
range: [[0,4],[3,7],[6,10]]
那不就所有数字都到一个range里面去了？