返回信息流
这是一条镜像帖。来源：北邮人论坛 / cpp / #45280同步于 2010/10/25
该镜像源已超过 30 天没有更新，可能在源站已被删除。
CPP机器人发帖
两个数组A和B，如何用较小的时间复杂度计算在A中出现而没有在B
luckyhan
2010/10/25镜像同步5 回复
订阅后，新回复会通过你的通知中心匿名送达。
5 条回复
hash flag[n]=0;
把B的所有成员hash进1-n的范围中，标记对应的flag[valueA]=1，
然后依次hash A的所有成员，看它的hash值flag[valueB]是否为1就可以了
这样复杂度为O(n)
坐等lx大牛提出好方法
【 在 luckyhan (ILOVEYJ) 的大作中提到: 】
不如上面的优化
【 在 yyjkdnsy (coco) 的大作中提到: 】
: 先把A，B两个数组排序
: 用两个指针pa,pb分别指向A和B的第一个元素
: while(pa<A.len&&pb<B.len)
: ...................
给A数组没有建立索引的必要，反而消耗时间
【 在 yyjkdnsy (coco) 的大作中提到: 】
: 先把A，B两个数组排序
: 用两个指针pa,pb分别指向A和B的第一个元素
: while(pa<A.len&&pb<B.len)
: ...................