iOS算法题-使用函数实现合并两个有序数组

本题要求：合并后元素不重复，时间复杂度为0(n)，并且要求资源消耗最小。

示例：

NSArray * arr1 = @[@1,@2,@5,@6,@8,@10,@15];
NSArray * arr2 = @[@2,@4,@5,@7,@10,@13,@15,@17,@19];
//输出结果：( 1,2,4,5,6,7,8,10,13,15,17,19)

思路：

要得到上面这个结果有千百种方式，但作为程序员应坚持“没有最优只有更优”才能不断进步。
要达到时间复杂度最优，我想应该是从两个数组的第一个元素开始，分别每组中取一个元素，然后进行大小比较，将较大或较小的元素存入新数组中，被取的那个数组在下一轮比较时直接取后面一个元素进行比较，依次遍历，一遍即可，同时完成排序和去重任务。

OC代码实现：

-  (NSArray * )mergeArray:(NSArray *)arr1 arrary:(NSArray *)arr2 {

    //为了严谨需要对 arr1、arr2做空值判断
    if ([arr1 count] == 0 && [arr2 count] == 0) {
        return nil;
    }
    if ([arr1 count] == 0) {
        return arr2;
    }
    if ([arr2 count] == 0) {
        return arr1;
    }

    NSInteger count1 = [arr1 count];
    NSInteger count2 = [arr2 count];
    //合并后的数组最大元素个数,提前预设mArr容量。
    NSMutableArray * mArr = [NSMutableArray arrayWithCapacity:count1+count2];
    //用于记录元素下标
    NSInteger idx1 = 0;
    NSInteger idx2 = 0;
    while (idx1 < count1 && idx2 < count2) {
        
        if ([arr1[idx1] integerValue] < [arr2[idx2] integerValue]) {
            [mArr addObject:arr1[idx1]];
            idx1 ++;
        }else if ([arr1[idx1] integerValue] > [arr2[idx2] integerValue]) {
            [mArr addObject:arr2[idx2]];
            idx2 ++;
        }else{
            //所取两个元素相等，去重
            [mArr addObject:arr1[idx1]];
            idx1 ++;
            idx2 ++;
        }
        
       //当arr1被全部取完，直接将arr2剩余的元素添加到新数组中
        if (idx1 >= count1) {
            while (idx2 < count2) {
                [mArr addObject:arr2[idx2]];
                idx2 ++;
            }
        }
        
       //当arr2被全部取完，直接将arr1剩余的元素添加到新数组中
        if (idx2 >= count2) {
            while (idx1 < count1) {
                [mArr addObject:arr1[idx1]];
                idx1 ++;
            }
        }
    }
    
    //NSLog(@"mArr== %@",mArr);
    return [mArr copy];
}

注意事项：

在实际开发中mArr可能是一个全局变量或者成员变量，并且涉及到多线程读写，这时程序的安全性很重要，读写时需要考虑对mArr加锁处理。

@synchronized (obj) {
            [mArr addObject:arr1[idx1]];
        }