使用一个数组过滤另一个数组

话不多说,直接上代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
NSMutableArray *resultArray = [[NSMutableArray alloc] init];
NSArray *array = @[@"a",@"a",@"c",@"d",@"e",@"f",@"g",@"h"];
NSArray *secondArray = @[@"a", @"c", @"f"];
int j = 0;
for (int i = 0; i < [array count]; ++i)
{
NSString *firstString = array[i];
NSString *secondString = secondArray[j];
if ([firstString isEqualToString:secondString]) {
[resultArray addObject:firstString];
}
else if ([firstString compare:secondString] == NSOrderedDescending)
{
if (j == [secondArray count] - 1)
{
break;
}
for (int k = j + 1; k < [secondArray count]; ++k)
{
secondString = secondArray[k];
if ([firstString isEqualToString:secondString])
{
j = k;
[resultArray addObject:firstString];
break;
}
else if([firstString compare:secondString] == NSOrderedAscending)
{
j = k;
break;
}
j = k;
}
}
}
NSLog(@"%@", resultArray);

我们来看看算法的复杂度:

如果做两个数组的遍历,显然算法复杂度为:O(m * n)

使用上述的办法需要先将两个数组进行排序(假设使用快排),因此算法的复杂度为:O(n(logn + n) + m(logm + m)) = O(nlogn + mlogm)