求两个数组的交，并，差，补有什么复杂度较低的算法?

Question

如题，希望有个复杂度较低的算法，indexOf，includes本身也是遍历，算不上复杂度低。new Set是语法糖，也不能算。用ES5实现，不知道有什么复杂度低于o(n*m)的算法？

Answer 1

两个数组的交并差补本来就是个复杂的问题，你还没限定数组的元素是啥，对象你要不要判等？数字和字符串能不能隐式转换？set是写进规范里的，为啥算语法糖？只能用es5，还不能用indexOf，includes，我就不知道用哪些算复杂度低？最关键还要复杂度低于o(nm) 复杂度低于o(nm) 复杂度低于o(n*m)在没给出任何条件却给出这么多限定条件的情况下题主你想想吧，反正我能力有限，想不出来。要不你写出来让大家瞅瞅，大家伙给你点赞~(^o^)/~

Answer 2

并 = function(A, B) {    d = {}    set = []    for (k in A) {        if (!(A[k] in d)){set.push(A[k])}        d[A[k]] = k    }    for (k in B) {        if (!(B[k] in d)){set.push(B[k])}        d[B[k]] = k    }    return set}交 = function(A, B) {    d = {}    set = []    for (k in A) {        d[A[k]] = k    }    for (k in B) {        if (B[k] in d){set.push(B[k])}        d[B[k]] = k    }    return set}差 = function(A, B) {    d = {}    set = []    for (k in B) {        d[B[k]] = k    }    for (k in A) {        if (!(A[k] in d)){set.push(A[k])}        d[A[k]] = k    }    return set}补 = function(A, B) {    return 差(B, A)}> 并([1,2],[1,3,5])[ 1, 2, 3, 5 ]> 差([1,2],[1,3,5])[ 2 ]> 交([1,2],[1,3,5])[ 1 ]> 补([1,2],[1,3,5])[ 3, 5 ]>