迁移自开源中国
在两个集合（万级别的数据量）中，找出相同的元素，并保存到一个集合中。
第一反应：两重循环解决问题，对，问题是可以解决，但是通过小括号中的提示可以看出，明显是在考效率的问题。
所以这种O(n^2)的时间复杂度是不行的。
继续想了一下：一次循环，遍历其中一个集合，拿集合中的元素去第二个集合中通过二分查找法查找，确定是否重复。
所以这种时间复杂度是：O(n*logn),较之前好些，但是还有更好的，可以是O(n)嘛？
经过面试官的提醒：首先对两个集合按照升序排列，再对两个集合定义各自的游标，一次循环，通过游标查找相同元素，原理是：如果从A集合中取出的元素小于B集合中的元素，那么将A的游标下移；如果相等则将元素存入第三个集合中，并且将A的游标下移；如果大于B集合中的元素，则将B的游标下移；直到遍历完某一个集合为止。
如果有更好的还请多多指教。
NSArray *array1 = @[@(1), @(3), @(5), @(7), @(10), @(30)];
NSArray *array2 = @[@(3), @(7), @(30)];
NSMutableArray *array = [NSMutableArray array];
int index1 = 0;
int index2 = 0;
while (YES) {
NSNumber *n1 = nil;
if (index1 < array1.count) {
n1 = array1[index1];
}
NSNumber *n2 = nil;
if (index2 < array2.count) {
n2 = array2[index2];
}
if (n1 == nil || n2 == nil) {
break;
} else {
NSComparisonResult result = [n1 compare:n2];
if (result == NSOrderedAscending) {
index1++;
} else if (result == NSOrderedSame) {
[array addObject:n1];
index1++;
} else {
index2++;
}
}
}
for (NSNumber *n in array) {
NSLog(@"%@", n);
}
