一道算法面试题

原创
2015/08/12 12:16
阅读数 196

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

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

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



展开阅读全文
打赏
0
10 收藏
分享
加载中
更多评论
打赏
0 评论
10 收藏
0
分享
返回顶部
顶部