回 帖 发 新 帖 刷新版面

主题:[讨论]讨论个算法问题。

CheckData数组有几下几个数据:Letter,11*17,A4,A5,B4
Data数组有几个下个数据:     Letter,11*17,A5,A5,Legal
两个数组内的数据都是随机排放,无排序。

比较之后得到的结果是: Data array doesn't include data: B4
                       Data array include more data: Legal

采用什么算法可以使时间,空间复杂度较小。

回复列表 (共2个回复)

沙发

方法一:
sizeA = A.size();
sizeB = B.size();

totalA = 2 的 sizeA 次方 -1 (totalA 以二进制形式表示)
totalB = 2 的 sizeB 次方 -1 (totalB 以二进制形式表示)

for (int indexB = 0; indexB < sizeB; indexB++)
{
     for(int indexA = 0; indexA < sizeA; indexA++)
     {
          if ( B[indexB] == A[indexA])
          {
               totalA = totalA 异或 (2的indexA次方)
               totalB = totalB 异或 (2的indexB次方)
          }
     }
}
解析(totalA) {例如11的到的结果是0,1 即2的0次方和2的1次方}
解析(totalB) {同上}
最后根据totalA的解析结果是B doesn't include data
    根据totalB的解析结果是B include more data

空间复杂度比较低,但是时间复杂度o(n的平方)
不知道有没有好的算法呢。

板凳

nlogn排序,n扫描,总时间nlogn,空间n

我来回复

您尚未登录,请登录后再回复。点此登录或注册