脸家实习

xiaolingf 发表于 2018-2-12 13:34
你想在哪一步用双指针？

我做法是输入是两个二维数组，二维数组每行两个数，index，index对应的value（这个和你list内的元素表示方式一样）。因为我默认index是升序排的，这样就可以用双指针比较索引了。

sugar 发表于 2018-2-12 13:39
我做法是输入是两个二维数组，二维数组每行两个数，index，index对应的value（这个和你list内的元素表示 ...

可以呀 我也是这样做的

xiaolingf 发表于 2018-2-12 13:41
可以呀 我也是这样做的

最后问用改用map存好不好（我用的list存），我觉得时间复杂度一样啊

我是看到这个才好奇你是什么做法的，如果用map，时间复杂度还一样的话，只能用treemap吧？不然index无序。

sugar 发表于 2018-2-12 13:47
我是看到这个才好奇你是什么做法的，如果用map，时间复杂度还一样的话，只能用treemap吧？不然index无 ...

我没有用map做。。就是你说的做法 不过用list存

xiaolingf 发表于 2018-2-12 13:48
我没有用map做。。就是你说的做法 不过用list存

我的意思是，那个follow up，你不是觉得用map时间复杂度一样吗？
然后我就想除非用treemap，不然时间复杂度会高不少。

sugar 发表于 2018-2-12 13:53
我的意思是，那个follow up，你不是觉得用map时间复杂度一样吗？
然后我就想除非用treemap，不然时间复 ...

可以以第一个map为基准 遍历每个key 然后看第二个map里是否有相同的key 这样的话还是linear time 我是这样理解的 欢迎指正哈

xiaolingf 发表于 2018-2-12 13:57
可以以第一个map为基准 遍历每个key 然后看第二个map里是否有相同的key 这样的话还是linear time 我是这 ...

哦哦，这样的确是linear time，刚才想偏了。谢谢耐心回复！

sugar 发表于 2018-2-12 14:01
哦哦，这样的确是linear time，刚才想偏了。谢谢耐心回复！

不客气 加油哈 有问题再讨论

xiaolingf 发表于 2018-2-12 14:04
不客气 加油哈 有问题再讨论

就来问follow up，先是时空复杂度，然后你的方法可以怎么提高

如果用双指针做了，还能怎么优化啊（如果不加其他条件的话）

sugar 发表于 2018-2-12 14:15
如果用双指针做了，还能怎么优化啊（如果不加其他条件的话）

我想的就是一个特别大的时候用binary search