iOS常用算法之两个有序数组合并, 要求时间复杂度为0(n)

青旅半醒 2023-08-17 17:16 70阅读 0赞

思路: 常规思路: 先将一个数组作为合并后的数组, 然后遍历第二个数组的每项元素, 一一对比, 直到找到合适的, 就插入进去;

简单思路: 设置数组C, 对比A和B数组的首项元素, 找到最小的, 就放入数组C,依次进行下去.

代码如下:

- (NSArray *)mergeOrderArrayWithFirstArray: (NSMutableArray *)array1 secondArray: (NSMutableArray *)array2 {
        // 全为空不处理
        if (!array1.count && !array2.count) {
            return @[];
        }
        // 一个为空返回另外一个
        if (!array1.count) {
            return array2;
        }
        if (!array2.count) {
            return array1;
        }
        NSMutableArray *endArray = [NSMutableArray array];
        while (1) {
            if ([array1[0] integerValue] < [array2[0] integerValue]) {
                [endArray addObject:array1[0]];
                [array1 removeObjectAtIndex:0];
            }else  {
                [endArray addObject:array2[0]];
                [array2 removeObjectAtIndex:0];
            }
            if (!array1.count) {
                [endArray addObjectsFromArray:array2];
                break;
            }
            if (!array2.count) {
                [endArray addObjectsFromArray:array1];
                break;
            }
        }
        return endArray;
    }

执行代码, 输入输出结果如下:

![826619-20190717204057662-1987009972.png][]

转载于:https://www.cnblogs.com/jgCho/p/11203508.html

[826619-20190717204057662-1987009972.png]: /images/20230808/51b2038cbb6641e98d2ff53135667794.png