谷歌电面

问了两个题
一个题是算一个完全二叉树的结点个数

您好！
本帖隐藏的内容需要积分高于 150 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 150 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Popular Interview Questions from Top Companies

. 1point 3 acres

楼主你也才105积分，让同为一百零几分的小白怎么看150的隐藏内容啊。求降分。。。

第二题我的想法是

1. 把M序列和N序列分别放到两个最小堆中，
2. 取两者较小的值，并pop，然后sum += 较小值 * 另一个堆的size
菜鸡发言，错了轻喷

vinf 发表于 2019-10-11 18:23
我有个想法，最大值从小到大考虑每行每列，每次将当前行/当前列的空格填上对应的最大值。

比如填一行时， ...

意思是考虑行列一起排序然后再计算嘛？
我感觉是可行的。
数据范围小的话，确实可以达到o（n+m)

但是感觉这个题主要时间复杂度就再排序上，一般的数据是不是那个log还是在的呀

我有个想法，最大值从小到大考虑每行每列，每次将当前行/当前列的空格填上对应的最大值。

比如填一行时，可以O(1)计算之前填过几列了，算出当前需要填的格子数，统计答案。

除掉排序整体的时间是O(n+m)，如果数字比较小，可以用桶排把整体的复杂度变成O(n+m)。

5555看不到

lt0506 发表于 2019-10-11 21:46
第二题我的想法是

1. 把M序列和N序列分别放到两个最小堆中，

这样的话，时间复杂度是不是也是nlogn的呀？

becky_w 发表于 2019-10-12 14:40
这样的话，时间复杂度是不是也是nlogn的呀？

严格来说不是，但是差别不大。楼主是校招还是社招面试啊

lt0506 发表于 2019-10-12 16:04
严格来说不是，但是差别不大。楼主是校招还是社招面试啊

校招-------------------

becky_w 发表于 2019/10/12 14:52:09
意思是考虑行列一起排序然后再计算嘛？
我感觉是可行的。
数据范围小的话，确实可以达到o（n+m)

但是感觉这个题主要时间复杂度就再排序上，一般的数据是不是那个log还是在的呀

是的，在不限制数据的情况下是有log的。不过只要是int范围内的整数，就可以用基数排序做到O(n)的复杂度，就是常数比较大。