coursera OA 可以重复做，什么鬼

今天做了coursera的OA，很不幸，遇到了第三个帖子里的那道coding题，然后就有两个case超时了。最后改来改去

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

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

示我已经做过了。但这次这个OA，重复点进去还可以重新开始做，而且题目还换了。

sapphirew 发表于 2016-8-26 11:31
时间复杂度其实可以做到O(n + max(nums[]) - min(nums[]))

补充内容 (2016-8-26 11:32):

新开的数组里面的元素应该是有序的吧，时间复杂度不应该是O(n*log(新数组的长度)）？

sapphirew 发表于 2016-8-24 10:24
求问楼主第二次做的题目，谢啦

木有截图。 第二次做的coding题目描述太长了，大概就是，输入一个全部是正数的数组，然后进行循环，在每次循环中，用数组中最小的数去减数组的每一个非0的数，这样就改变了数组中的数，直到数组中所有的数变成0，循环结束。输出就是每次循环里当前数组的非0的数字的个数。

sapphirew 发表于 2016-8-26 11:37
假设数组是[2,2,1,3,3],这样可以构建一个size为3的array做频数统计，得到一个[1,2,2]的array分别代表1，2 ...

就是用哈希表统计各个数出现的频率。在java里，用TreeMap;在C++里，用map；这两个数据结构都是按照key的大小排好序的。map建立好之后，直接遍历map就行，然后在每层循环里减去key所对应的value。

求问楼主第二次做的题目，谢啦

感谢lz分享

谎言之躯 发表于 2016-8-24 13:51
木有截图。 第二次做的coding题目描述太长了，大概就是，输入一个全部是正数的数组，然后进行循环，在每 ...

谢谢分享~没有想到什么很好的解法，先sort再计算仿佛也没有降低复杂度，话说楼主是brute force做的吗

sapphirew 发表于 2016-8-25 06:29
谢谢分享~没有想到什么很好的解法，先sort再计算仿佛也没有降低复杂度，话说楼主是brute force做的吗

不用排序呀，就是线性扫描数组，算是暴力吧。

我做了三次。。

sapphirew 发表于 2016-8-25 06:29
谢谢分享~没有想到什么很好的解法，先sort再计算仿佛也没有降低复杂度，话说楼主是brute force做的吗

多开一个数组存每个数的count，然后再过一遍这个数组，每次用总个数减去count，存起来，时间复杂度O(数组size+数的范围）

todayand 发表于 2016-8-25 14:14
多开一个数组存每个数的count，然后再过一遍这个数组，每次用总个数减去count，存起来，时间复杂度O(数组 ...

大神！能否再详细解释下咩？！

todayand 发表于 2016-8-25 14:14
多开一个数组存每个数的count，然后再过一遍这个数组，每次用总个数减去count，存起来，时间复杂度O(数组 ...

厉害啊。。这样算非零的个数时就不用考虑具体的数值了，666