脸书 电面

第二題看起來很像 散四期 變體。Instead of returning the elements, it asked for the frequencies of the elements. O(N)可以用quickselect或bucket sort做

安然的拐子 发表于 2021-09-05 19:18:06
请问这题咋quick select啊？我感觉是sliding window加两个count？

Quick select最优的情况是N，最差是N^2，它不稳定

第二题有个思路，先扫一遍， 然后记录每个连续长度的个数和连续长度 用map<integer, integer>（如果需要求出具体的哪些数字，用map<integer, list<integer>>
然后根据需要，可以加入priorityqueue里边，按照长度排序，或者开一个list<integer>[] 用bucket sort做。

第二题要是同一个数有多个不同的连续长度怎么办？比如221111133222444， 连续的2有长度2也有长度3。这种case会存在吗？如果每个数的连续长度都是唯一的话，那就直接用hashmap记录就可以了，然后就是LC347 TopK freq。

在哪里写代码 codility吗?还是google doc