将两个排序号的数组合并

注意这里是已经排序好的数组，假如说有如下两个数组：

NSArray<NSNumber *> *array1 = @[@"1",@"2",@"3",@"4",@"5"];
NSArray<NSNumber *> *array2 = @[@"1",@"2",@"3",@"4",@"5",@"5",@"5",@"5",@"5"];

必然，出现两个数组要做比较时，最暴力的一种方式就是循环嵌套循环，但是时间效率是 O(n²)，还有一种相对来说好一点的，时间复杂度大约是 O(n)。

实现思路：

1. 因为是已经排好序的数组，如果数组 array1 中的某个下标为 index1的元素小于数组array2中某个下标为 index2的元素，那么下标为index1的元素 一定小于index2 后面的所有元素。
2. 做 dowhile 循环:
   如果 index1 指向的元素小于 index2指向的元素，将index1指向的元素拷贝到新数组中并且 index1++
   如果index1 指向的元素等于index2指向的元素，将index1和index2指向的元素拷贝到新数组，并且index1++，index2++
   如果index1指向的元素小于index2指向的元素，将index2指向的元素拷贝到新数组中并且 index2++
   结束条件是任何一个数组被遍历完了都结束，如果有剩下的元素，那么都是大于等于在循环中添加的最后一个元素的。
3. 如果array1中的元素都取完了，那么判断一下array2中的元素是否取完，如果没有，则直接将array2中剩余的元素添加到新的数组中。此时直接可以用array1里面的数值判断是否小于 array数组的个数，在之前的循环中已经将 array1 做了 ++ 的操作，如果还没取完，for 循环的第一次也不用做++的操作，因为之前的循环中已经加过了。

具体的实现代码如下：

- (void)viewDidLoad {
    [super viewDidLoad];
    
    NSArray<NSNumber *> *array1 = @[@"1",@"2",@"3",@"4",@"5"];
    NSArray<NSNumber *> *array2 = @[@"1",@"2",@"3",@"4",@"5",@"5",@"5",@"5",@"5"];
    
    NSMutableArray<NSNumber *> *sumArray = [NSMutableArray arrayWithCapacity:array1.count + array2.count];
    int index1 = 0, index2 = 0;
    do {
        if (array1[index1] < array2[index2]) {
            [sumArray addObject:array1[index1]];
            index1++;
        } else if(array1[index1] == array2[index2]) {
            [sumArray addObject:array1[index1]];
            [sumArray addObject:array2[index2]];
            index1++, index2++;
        } else {
            [sumArray addObject:array2[index2]];
            index2++;
        }
    } while (index1<array1.count && index2<array2.count);

    //循环结束后，判断是否还有数组未结束，此处有两种情况，两个循环都结束，其中有一个结束
    if (index1 < array1.count) {
        for (; index1<array1.count; index1++) {
            [sumArray addObject:array1[index1]];
        }
    } else if(index2 < array2.count) {
        for (; index2<array2.count; index2++) {
            [sumArray addObject:array2[index2]];
        }
    }
    
    NSLog(@"sumArray: %@", sumArray);
}

执行结果如下：

两个排序好的数组合并.png