有这么一道题，移除数组中所有不符合要求的元素。

因为我目前是个iOS开发，所以这道题的内容我用OC语言来重新描述下：

假设有一个NSMutableArray，里边存放了n个Person的实例，Person里有个属性age，现在要求你写个方法，移除数组中所有age < 18的Person。

乍一看，很简单对吧？

一般的写法

遇到类似问题，我们一般都是直接写个循环，然后在循环里边进行判断，移除不符合要求的元素，大致的写法如下：

for (int i = 0; i < arr.count; i++) {
    Person *person = arr[i];
    if (person.age < 18){
        [arr removeObjectAtIndex:i];
        I--;
    }
}

这里有一点需要注意的是，每次移除数组的元素之后，当前索引后边的元素索引都会变，所以这时候需要将i减一，否则会有部分元素无法遍历到。

看上去完成了要求，可是如果你这么写的话，我只能给你打一个60分，因为完成了任务，所以及格了，但仅仅完成了任务，所以只是及格。

这样的写法，只考虑到了完成任务本身，而没考虑到算法的效率问题。上边的写法，时间复杂度是O(n²)，而我们的目标是，要写出时间复杂度为O(n)的算法。

等等...上边的写法只有一层循环，主要的操作就是移除元素，时间复杂度应该是O(n)啊，是不是那里算错了？

那么问题出在哪了？我们知道，当我们在移除数组的元素之后，实际上我们是需要循环的将之后的元素全都往前移一位的，如下图所示：

移除当前元素后，需要将之后的元素向前移动一位

这是典型的前n项和公式，计算结果是(1+n)*n/2，所以时间复杂度是O(n²)

另一种写法

我们很容易会想到另一个比较巧的写法，就是倒着循环：

for (int i = arr.count - 1; i >= 0 ; i--) {
    Person *person = arr[i];
    if (person.age < 18){
        [arr removeObjectAtIndex:i];
    }
}

这样写的好处是，可以避免索引乱掉的问题，因为，当你移除掉当前元素之后，影响的是后边的元素，而因为你是倒着循环的，后边的元素你已经遍历过了，所以不会有影响。

但最关键的是，这种写法看上去要比上一个方法效率高点，因为是倒着遍历的，所以当我们移除当前元素，将之后的元素向前移动的时候，由于后边不符合要求的元素已经被我们移除了，所以避免了没有必要的移动。反过来，正循环每次移除元素后，需要把后边的所有元素前移，即便有些元素也是要移除的不符合要求的，也不例外。

举个例子就是，如果数组里的所有元素都是需要移除的，正循的时间复杂度是O(n²)，而倒循环则达到了惊人的O(n)，因为后边的元素都已经移除了，不需要进行前移操作。

如果你这么写，我会给你65分，毕竟这种写法解决了索引的问题，比正循环少了一个i--的操作，多少会有些效率的提高，可也只能比前一种方法多5分，因为它仍然没有突破O(n²)的坎儿，并且，至少在iOS中，这两种写法几乎是没有任何区别的。

我们刚才认为的效率高点，其实并不存在，因为，iOS的数组已经针对这样的问题进行了优化。

NSMutableArray的底层实现

首先，NSMutableArray的底层是C数组；

NSMutableArray使用了环形缓冲区的概念，简单来说就是，数组还是那个数组，但是firstObject可以在C数组的任何位置。

NSMutableArray内部有三个属性:
_size：数组大小。
_used：已使用部分大小。
_offset：firstObject所在的位置。

假设有这么一个数组：

现在，我们删除第4个元素：

这个比较好理解，接下来我们删除第1个元素，按照正常逻辑，应该是这样的：

但实际上，NSMutableArray对增删操作的内存移动做了优化，它会进行计算，然后以最小的内存移动代价来完成这次移除操作，所以实际上是这样的：

现在我们继续移除1，2，3位置的元素，然后再在6，7，8，9位置上添加新的元素：

如果我们此时再向数组尾部添加一个元素，则会变成这样：

跨过O(n²)的坎儿

现在我们明白了，因为iOS数组底层的优化，前两种方法的时间复杂度是一样的，不管是从哪头开始遍历，NSMutableArray都会用最小的开销来移动元素。

因此，我们想到了第三种实现方式，创建一个新的数组，将原数组中符合要求的元素移动到新的数组中，并将原数组销毁，这样，每次循环只需要将元素移动到另一个数组，再也不用担心内存移动所带来的消耗了！代码大致如下：

NSMutableArray *newArray = [NSMutableArray arrayWithCapacity:originArray.count];
for (int i = 0; i < originArray.count ; i++) {
    Person *person = originArray[I];
    if (person.age >= 18){
        [newArray addObject:person];
    }
}

好了，现在时间复杂度是O(n)了！是不是很有成就感！然而，这个O(n)是有代价的...

虽然时间复杂度达到O(n)了，但是相应的，空间复杂度也从O(0)变成O(n)了。所以，这只是牺牲空间换时间，而时间和空间的重要性，会根据实际的场景而变化，所以并不存在谁一定比谁重要（虽然大部分情况下大家认为时间更重要）。

但作为第一个达到O(n)的算法，我们可以将之作为备选方案，这里标记为空间换O(n)算法。

降低时间复杂度和空间复杂度的重要性

也许有些人会不以为然，时间复杂度和空间复杂度真的有那么重要么？就这几个元素，真的有必要搞得这么复杂？

其实是很有必要的，如果数组里只有十几个元素，可能O(n)和O(n²)的差距不大，但如果有几万，乃至于上百万个元素呢？为了节省时间而需要多开辟这么大的空间是不理智的，而为了节省空间让计算的时间成指数倍增加也是不能接受的。

也许还有人会说，作为客户端，感觉日常开发中，即便遇到了这样的需求，也不会真的需要操作大量的数据。

我想说的是，作为一个优秀的程序员，我们不能放过任何一个微小的细节，虽然优化过后带来的收益可能微乎其微，但积少成多，也许就能看到明显的效率提升，就能改善用户的体验。

退一步说，万一以后我们转岗做其他端了呢？对吧~

下面我们来实际模拟下，看一下O(n)和O(n²)的差距到底有多大。

我们随机生成十万个Person，分别用第一个算法和空间换O(n)算法来移除，看看时间上能差多少：

可以看到，O(n)的算法只用了0.012秒，而O(n²)则用了0.206秒，时间上相差了16.9倍！

而O(n)算法的空间开销则达到了781KB！

那么，有没有时间复杂度O(n)，空间复杂度O(0)的方案呢？有的！

快速排序

在讲下一个方案之前，我先讲一下快速排序，可能大家已经猜到了，突破O(n²)的关键，就在快排的核心思想中。

快排的核心思想是，找一个基准元素，将比基准元素大的元素放到基准元素的右边，将比基准元素小的元素放到基准元素的左边，这样一圈下来，左边的部分就是全都小于基准元素的元素，右边是全都大于的。然后再对左右两边的部分重复上述过程，直到最后一个元素。下面进行图解说明：

假设我们有个未排序的数组：

我们需要定义两个变量left和right，分别代表数组的第一个元素和最后一个元素的索引值，然后，将第一个元素18作为基准元素。

接下来，right从后向前遍历，找到第一个小于基准元素的元素并记录，left从前向后遍历，找到第一个大于基准元素的元素并记录（注意，right和left遍历的先后顺序会影响到之后的处理逻辑，大家可以思考下为什么），然后，交换这两个位置的元素：

然后将基准元素与left(right)所在的元素调换位置：

真·跨过O(n²)的坎儿

知道了快排的原理，我们就可以对我们的算法进行升级了，不过，毕竟我们的需求不是排序，所以实现上会稍微有些不同。

仔细一想，本题中的18岁就是快排中的基准元素，按照这个思想，假设我们有个数组：

我们定义两个变量left和right，分别指向数组的头和尾：

image.png

然后left向后遍历，找到第一个不符合要求的Person，right向前遍历，找到第一个符合要求的Person（这里的先后顺序依然会影响后边的逻辑）：

然后交换这两个Person：

重复这个过程，直到left和right相遇：

此时，从left(right)到数组末尾的元素，就全都是不符合的了，然后我们将这些不符合的元素全部移除，得到最终结果：

大致代码如下：

- (void)removeInconformityElementOfArray:(NSMutableArray *)arr{
    int left = 0;
    int right = arr.count - 1;
    do {
        while (left <= right) {
            Person *person = arr[left];
            if (person.age < 18){
                //找到了不符合的元素
                break;
            }
            left++;
        }
        while (left < right) {
            Person *person = arr[right];
            if (person.age >= 18){
                //找到了符合的元素
                [arr exchangeObjectAtIndex:left withObjectAtIndex:right];
                left++;
                if (left != right - 1) {
                    right--;
                }
                break;
            }
            right--;
        }
    } while (left < right);
    [arr removeObjectsInRange:NSMakeRange(left, arr.count - left)];
}

不需要多余的内存移动，只需要简单的元素交换，时间复杂度O(n)。没有多余的内存开销，空间复杂度O(0)，现在，我们找到了第二个备选方案，我们标记为不稳定O(n)算法。

是的，这个算法是不稳定的。

排序算法的稳定性指的是，排序结束后，相等元素的相对顺序是否保持不变。如果不变，那么我们说这个排序算法是稳定的。

我们知道，快速排序是不稳定的，因为交换的过程，可能会导致相同的元素的位置发生变化，如下图所示：

交换过后，两个“14”的相对位置发生了变化

因此，上边的算法也是不稳定的，用上边的算法操作后的数组，里边元素的顺序会乱掉。

试想，如果这是n个人在排队买票，现在临时决定让未成年人去另一个窗口排队了，所以需要在当前队列中移除未成年人，可是当移除了所有的未成年人之后，队伍乱掉了，刚才排第一的人现在在队尾😱，是不是很可怕！

真·稳定的·跨过O(n²)的坎儿

那么，如何写出一个稳定的O(n)算法呢？

快排虽然不稳定，但给我们提供了正确的思路，我们能不能在快排的思想基础上，换个稳定的实现方式呢？答案是肯定的。

既然从两边往中间走不稳定，那么我们可以尝试都从一边走，不符合标准的从左边开始找，符合的也从左边找，这样是不是就避免了不稳定性呢？让我们来看下。

首先，依然是那个数组：

image.png

这次，我们不用left和right了，我们定义两个变量retain（保留）和remove（移除），我们先将remove设置为0：

然后向右遍历，找到第一个不符合要求的元素：

因为remove之前的一定都是符合要求的元素，所以直接将retain的初始值赋值为remove + 1：

然后找到第一个符合要求的元素：

交换这两个元素：

重复上述步骤，直到retain完成遍历：

移除remove以及之后的所有元素，得到最终结果：

代码大致如下：

- (void)removeInconformityElementOfArray:(NSMutableArray *)arr{
    //记录需要移除的元素
    int remove = 0;
    for (int i = 0; i < arr.count; i++) {
        Person *person = arr[i];
        if (person.age >= 18){
            [arr exchangeObjectAtIndex:remove withObjectAtIndex:i];
            remove++;
        }
    }
    //移除不符合的元素并结束
    [arr removeObjectsInRange:NSMakeRange(remove, arr.count - remove)];
}

这是最后一个备选方案，我们标记为稳定O(n)算法。

三个备选方案的对比

现在，我们再来模拟一下，还是100000个Person，用O(n²)算法和三个备选方案作对比。

这次我们对生成Person实例的策略进行了调整，弃用了完全随机的方案，取而代之的是，将奇数索引的age设置为17，偶数索引的设置为19，这样，就能保证生成的实例中，有一半是需要移除的。

这么做的原因是，空间换O(n)算法主要的时间开销是将符合的元素移动到新的数组，而另外的两个O(n)算法是将不符合的元素交换到数组末尾并移除。因此，需要移除的元素越少，空间换O(n)算法执行的时间反而越长，反之亦然，为了得到更准确的数据，符合和不符合的元素数量要相等。

运行后的结果如下：

我们可以看到，O(n)和O(n²)的差距还是很显而易见的，不过，三个O(n)算法的耗时也是有一些差别的，下面我详细的分析下。

空间换O(n)算法是最快的，因为牺牲了空间，所以，该算法主要的时间开销是，将符合的元素放到新的数组，相当于只做了一次赋值操作，所以是最快的。

不稳定O(n)算法稍慢，因为该算法除了移除不符合的元素，还需要交换元素的位置，比空间换O(n)算法多了一些操作，所以会有一些额外的开销，不过差的并不多，大概多出了6.4%左右。

稳定O(n)算法最慢，比空间换O(n)算法大概多出了11.9%的时间，因为该算法相当于是在不稳定O(n)算法的基础上，又做了额外的元素交换。不稳定O(n)算法相当于是牺牲了稳定性来换取时间上的效率，下面举例来说明：

还是以本题为例，如图所示的数组，不稳定O(n)算法是直接交换不符合的元素11与最后一个元素19，只有一次交换就完成了任务，但是相应的，数组元素的顺序会乱掉，所以不稳定。

而稳定O(n)算法在找到了不符合的元素11之后，要先找到其后的第一个符合的元素50，并与之交换，然后继续寻找后边的其他符合的元素交换，直到结束。本例中进行了四次交换，正是那多出的三次交换，保证了算法的稳定性，但同时时间上也会稍慢一些。

时间复杂度和空间复杂度的取舍

那么，以上三个算法哪个最好呢？如果数组里的元素数量较少，我们可能就不太关心空间开销，空间换O(n)算法无疑是最棒的。对于大量数据的操作，就要看具体的使用场景（需求）了，那么你是否愿意牺牲11.9%的时间来节省大量的空间开销呢？如果对稳定性没要求，付出的代价可以更少。

又或者，当前场景下，需要移除的元素不会太多，那么看上去速度最快的空间换O(n)算法反而拖了后腿。

所以，还是要根据实际情况具体分析的。

结论就是，这三个算法都很优秀~在不同的使用场景，我都可以给你85分！

还想得更高的分怎么办？继续往下看~

继续优化

虽然这个算法已经很优秀了，但还是有一些问题，比如：

1. 没有对入参的异常情况进行处理，比如输入的是不可变数组，或者根本不是个数组。
2. 入参的数组没有判空。
3. 获取数组元素后，没有判断元素类型，如果数组有非Person的元素，就会crash。
4. 算法不通用，耦合了业务逻辑，只适用于判断Person的age。
5. 没有运用OC的特性，让算法更独立，架构更清晰。

下面我们针对这些问题进行优化。

添加对入参异常情况的处理：（+1分）

if (![arr isKindOfClass:NSMutableArray.class]){
    return;
}

添加数组判空逻辑：（+1分）

if (!arr.count){
    return;
}

判断元素类型：（+1分）

if (![obj isKindOfClass:Person.class]){
    //遇到数据类型不匹配问题,根据业务需求返回
    return YES;
}
return ((Person *)obj).age < 18;

算法解耦，我们可以仿照NSMutableArray的排序方法进行优化，这里使用Block的方式，修改后的方法名如下：（这个得加2分！）

- (void)removeInconformityElementOfArray:(NSMutableArray *)arr
                            compareBlock:(BOOL (^)(id obj1,id obj2))compareBlock

相应的，原来方法里判断的地方就变成了这样：

if (judgmentBlock(arr[remove])){
    //找到了不符合的元素
    break;
}

调用大概是这个样子的：

[self removeInconformityElementOfArray:arr withJudgmentBlock:^BOOL(id obj) {
    if (![obj isKindOfClass:Person.class]){
        //遇到数据类型不匹配问题,根据业务需求返回
        return YES;
    }
    return ((Person *)obj).age < 18;
}];

下面重点说下运用OC特性这一点，我们知道，目前的方法是定义在我们需要操作数组的类里，显然这个方法放在这里是不合适的，如此通用的一个方法，应当服务更多的类才是。

于是我们定义了一个工具类XXXUtil，将这个方法变成了类方法，这样，需要的地方就都可以用了...但是这样还是不够好。

不好的原因有很多，比如，这个类应该放在哪？如何归类？这个类里还可以放一些什么方法？最关键的是，别人需要用的时候，他怎么知道有没有这样的方法？应该去哪个类里找？

这个时候，我们想到了OC的一个特性，Category，我们可以给NSMutableArray写一个Category，将这个方法放到Category当中，这样，我们就可以把它归类到CommonLib的Category分类当中，别人要用到了相似的功能，可以优先去找NSMutableArray的分类，看看有没有类似的功能，思路清晰，分类准确，寻找方便，架构清晰，很合理对不对~

下面我们继续对方法进行优化，首先我们创建个分类NSMutableArray+LSYRemoveElement，然后将方法修改后放到这个类中。最终的代码如下：

- (void)lsy_stabilizeRemoveInconformityElementWithJudgmentBlock:(BOOL (^)(id obj))judgmentBlock{
    if (![self isKindOfClass:NSMutableArray.class] || !self.count){
        return;
    }
    //记录需要移除的元素
    int remove = 0;
    for (int i = 0; i < self.count; i++) {
        if (!judgmentBlock(self[i])){
            [self exchangeObjectAtIndex:remove withObjectAtIndex:i];
            remove++;
        }
    }
    //移除不符合的元素并结束
    [self removeObjectsInRange:NSMakeRange(remove, self.count - remove)];
}

调用代码大致如下：

[arr lsy_removeInconformityElementWithJudgmentBlock:^BOOL(id  _Nonnull obj) {
    if (![obj isKindOfClass:Person.class]){
        //遇到数据类型不匹配问题,根据业务需求返回
        return YES;
    }
    return ((Person *)obj).age < 18;
}];

到此，优化完毕，我可以给你92分！

那么，还有可以优化的地方嘛？

其实还有...

emmm...别嫌烦啊，有时候，看着简单的事情，做起来确实可能会很麻烦。

看上去，该考虑的都考虑到了，那么还差什么呢？

我们还没有考虑线程安全问题啊！！！

如果全程只在一个线程操作，那么这个方法已经非常完美，可万一在移除的过程中，其他线程对数组做了增删改交换等操作呢？或者其他线程也调用了这个方法处理同一个数组会怎么样？所以线程安全是非常必要的。

保证线程安全的方式有很多种，具体如何实现，我这里就不举例了，因为有关多线程的东西太多了，以后可以慢慢讲。

还有最后一点...

最后一点要考虑的就是，如果数组里的元素太多，操作太耗时，就会导致卡顿。所以我们可以提供个同步和异步的选项，由使用者来决定是否要在子线程执行。

到此，我可以给你95分了！少给你5分是怕你骄傲！

Demo我已经上传到了GitHub，有兴趣的小伙伴可以下下来看看~

写在最后的话

刚工作的时候，我的一个领导曾经对我说过这样一句话：

不管你觉得你写的代码有多棒，也许你现在觉得已经是最好了，但三个月后再看，你依然能够找到很多可以优化的地方。

然后我用我的懒惰和退步向他证明了，他错了！

当然不是！其实是我明白了他这句话的意思，所谓没有最好，只有更好，所谓学无止境。我们现在觉得自己写的代码无可挑剔，是因为以我们现在的知识水平，还没找到更好的写法，随着我们技术水平的提高，我们一定能写出更好的代码~

所以，少给5分不是怕骄傲，是因为确实不知道满分是什么样子的。

最主要的是，万一有一天，有人用更好的写法反驳了我，我就可以理直气壮地说，“我不是没给自己打满分么😏”