coursera OA 可以重复做，什么鬼

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

时间复杂度其实可以做到O(n + max(nums[]) - min(nums[]))

补充内容 (2016-8-26 11:32):
哈哈。。其实和你说的一样，看岔了

Tommzy 发表于 2016-8-26 09:13
大神！能否再详细解释下咩？！

假设数组是[2,2,1,3,3],这样可以构建一个size为3的array做频数统计，得到一个[1,2,2]的array分别代表1，2，3出现的频数，每次最小的数字（min）减掉自己后变为0，比最小数字大的数减去min依旧还是正数，这样扫一遍这个array就可以得出答案[4，2，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。

谎言之躯 发表于 2016-8-26 12:28
就是用哈希表统计各个数出现的频率。在java里，用TreeMap;在C++里，用map；这两个数据结构都是按照key的 ...

用binary search tree复杂度变成O(nlogn), 考虑到worst case用数组存更优吧。

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

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

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

感谢楼主分享！！！

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

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

我觉得还是得排序呀 不然你哪里知道你的hash里哪个value是最小元素的个数~~~~

menghuanboluomi 发表于 2016-9-29 23:04
我觉得还是得排序呀 不然你哪里知道你的hash里哪个value是最小元素的个数~~~~

不用hash啊，一个array就行了

sapphirew 发表于 2016-9-30 09:52
不用hash啊，一个array就行了

不排序你怎么知道array里的某一个元素对应的是那个数字的出现次数？
[9, 2, 9, 3,5,6, 3,2]不排序给出array是？

补充内容 (2016-10-4 14:18):
倒是不用排序，但是可以用一个min-heap存（数字，次数）pair，这样每次pop出的元素一定是最小的数字和它的次数。不过这样时间复杂度跟排序量级上也差不多，入堆的的时候可能要调整顺序。但调整的次数比排序少

ymsf 发表于 2016-10-4 14:10
不排序你怎么知道array里的某一个元素对应的是那个数字的出现次数？
[9, 2, 9, 3,5,6, 3,2]不排序给出ar ...

请你仔细看上面的回复，也请你注意说话的语气。你的方法在array非常稀疏时适用。