Question

求两个数组的并集减去交集的部分，有什么好的算法

Answer 1

首先对较短的一个数组（设长度为a）建立平衡二叉搜索树（需要alog2（a）的时间）。
然后对另一个数组（设长度为b）的每一个元素，在a的搜索树中查找（需要blog2（a）的时间）。
所以总共需要alog2（a）＋blog2（a）的时间。
而2楼的算法需要ab的时间。
当b>a>4时，
a>2log2(a)
log2(a)<a-log2(a)
log2(a)/(a-log2(a))<1
alog2(a)/(a-log2(a))<a
又b>a
alog2(a)/(a-log2(a))<b
alog2(a)<ab-blog2(a)
alog2(a)+blog2(a)<ab
所以b>a>4时我的算法比2楼快。
当然，还有常数项的问题，上面的“快”只是渐进意义上的快。