题目描述

给定2个大小分别为n, m的整数集合,分别存放在两个数组中 int A[n], B[m],输出两个集合的交集。

1 1 收藏


直接登录
最新评论
  • 王念一 初三学生 03/17

    先对两个数组排序,然后遍历咯,这样时间复杂度是 T(n*lg(n) + m*lg(m) + n + m) ∈ O(N*lg(N))

    不过更狠的是,对于数据量足够大的时候,先将两数组合并然后再排序去重。

    可以证明,合并之后的排序总会在 n > 4^(n/(n+m)) + x^2 – m 时比分别排序快。

  • ﹎.   03/17

    如果有额外的内存空间,那么可以用空间换时间,考虑n和m的大小范围再决定用什么方法。