Google電面

can we convert double to a string and then use them as keys in hashmap? each key k takes number counts in range [k, k+1)

小A要当码农 发表于 2016-12-5 04:53
桶排序好像不太行吧，，除非你能维持桶内部有序。

桶排序後, 桶內部本來就是有序的.
目前感覺最好的方法就是先桶排序, 這樣整個數組就是有序的, 然後再用two pointer.
時間平均為O(n).

感觉是最优解了啊，可以考虑用整数桶优化，但是时间复杂度不会低于nlogn， 不明白为啥为挂？

david123bbs 发表于 2016-12-30 00:57
桶排序後, 桶內部本來就是有序的.
目前感覺最好的方法就是先桶排序, 這樣整個數組就是有序的, 然後再用t ...

他这个X不一定是整数啊

小A要当码农 发表于 2016-12-30 05:50
他这个X不一定是整数啊

整数桶计数，然后扫描一遍获取最大值的桶，所以答案一定至少是这个值。叫这个最大值为max1，然后扫描桶，当碰到i和i+1桶数目和大于max1的时候，只排序这两个桶的内容就可以了。这个做法只是优化，并不会降低时间复杂度

用hashmap key作为一个整数 代表这个整数到下个整数.99    然后存。 扫一遍再看那个key里value做多就好

zxj1987 发表于 2016-12-30 13:19
整数桶计数，然后扫描一遍获取最大值的桶，所以答案一定至少是这个值。叫这个最大值为max1，然后扫描桶， ...

喔喔 懂啦 多谢解释。 但是感觉这个优化的意义并不是很大呀。。

小A要当码农 发表于 2016-12-31 01:10
喔喔 懂啦 多谢解释。 但是感觉这个优化的意义并不是很大呀。。

是啊，所以不明白为什么LZ挂了

想了一下這題如果用two pointers的複雜度應該是O(nlogn)+O(n^2)
如果每個數字都很接近的話那要重複計算很多次