主题:[讨论]讨论个算法问题。
心灵鸡汤
[专家分:710] 发布于 2007-11-28 14:45:00
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
采用什么算法可以使时间,空间复杂度较小。
最后更新于:2007-11-28 14:52:00
回复列表 (共2个回复)
沙发
心灵鸡汤 [专家分:710] 发布于 2007-11-28 15:54:00
方法一:
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的平方)
不知道有没有好的算法呢。
板凳
FancyMouse [专家分:13680] 发布于 2007-11-30 17:54:00
nlogn排序,n扫描,总时间nlogn,空间n
我来回复