两个集合中找相同元素

迁移自开源中国

在两个集合（万级别的数据量）中，找出相同的元素，并保存到一个集合中。

第一反应：两重循环解决问题，对，问题是可以解决，但是通过小括号中的提示可以看出，明显是在考效率的问题。

所以这种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);
}