askpass

请输入暗号:


确定
交流中心 >>
查看主题
所有分类
教育/科学 求职/职场 生活/健康 旅游/出行 其他
  • Hash应该是时间最优了吧,两个数组都扫一遍,O(m+n)不可能再少了。但是空间上可能不是最小。因为交集需要开两个map。

    smilence
    smilence 回答
    7 年前
  • 想请教下lz是第一轮电面么?只有一道题?

    smilence
    smilence 回答
    7 年前
  • 看到有人提出如下解法,是有可能更优的:

     

    “返回交集当然有可能更好的算法,这要看array的size情况。比如,对第一个array中的每个元素在另一个array中做binary search看这个元素是不是存在,如果存的话在加入result集合,这样复杂度是m*log(n)。当m比较小n比较大的时候肯定是好于m+n的。

    而且,这个算法本身也可以做优化,每次在第二个array中查找的时候只要从比上一个处理的第一个array中元素大的位置开始找就可以了,所以有early termination的可能。”

    哈利利
    哈利利 回答
    7 年前
要发表回复,请先 登录或者注册

阿蘑多:收藏和分享喜欢的

>了解阿蘑多

  聊天广场:(鼠标移到左边框可调窗口大小)

聊天消息

最近在线用户

  • (我)
改名
发送
群名: *
说明:
是否公开:
暗号:
(*) 必填
要创建群组,还请先登录。