遷移自開源中國

在兩個(gè)集合（萬級(jí)別的數(shù)據(jù)量）中，找出相同的元素，并保存到一個(gè)集合中。

第一反應(yīng)：兩重循環(huán)解決問題，對(duì)，問題是可以解決，但是通過小括號(hào)中的提示可以看出，明顯是在考效率的問題。

所以這種O(n^2)的時(shí)間復(fù)雜度是不行的。

繼續(xù)想了一下：一次循環(huán)，遍歷其中一個(gè)集合，拿集合中的元素去第二個(gè)集合中通過二分查找法查找，確定是否重復(fù)。

所以這種時(shí)間復(fù)雜度是：O(n*logn),較之前好些，但是還有更好的，可以是O(n)嘛？

經(jīng)過面試官的提醒：首先對(duì)兩個(gè)集合按照升序排列，再對(duì)兩個(gè)集合定義各自的游標(biāo)，一次循環(huán)，通過游標(biāo)查找相同元素，原理是：如果從A集合中取出的元素小于B集合中的元素，那么將A的游標(biāo)下移；如果相等則將元素存入第三個(gè)集合中，并且將A的游標(biāo)下移；如果大于B集合中的元素，則將B的游標(biāo)下移；直到遍歷完某一個(gè)集合為止。

如果有更好的還請(qǐng)多多指教。

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);
}