有这么一道题，移除数组中所有不符合要求的元素。
因为我目前是个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)啊，是不是那里算错了？
那么问题出在哪了？我们知道，当我们在移除数组的元素之后，实际上我们是需要循环的将之后的元素全都往前移一位的，如下图所示：
移除当前元素后，需要将之后的元素向前移动一位
代码里之所以没有体现出来，是因为
OC的NSMutableArray已经帮我们做了这个工作，所以这样的写法实际上是有两层循环的，假设数组里有n个元素，每个元素都是需要移除的，那么第1次需要移动n次（移除当前元素，前移剩下的n-1个元素），第2次需要移动n-1次...第n次需要移动1次。
这是典型的前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相遇：
然后将基准元素与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分！
还想得更高的分怎么办？继续往下看~
继续优化
虽然这个算法已经很优秀了，但还是有一些问题，比如：
- 没有对入参的异常情况进行处理，比如输入的是不可变数组，或者根本不是个数组。
- 入参的数组没有判空。
- 获取数组元素后，没有判断元素类型，如果数组有非
Person的元素，就会crash。 - 算法不通用，耦合了业务逻辑，只适用于判断
Person的age。 - 没有运用
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分不是怕骄傲，是因为确实不知道满分是什么样子的。
最主要的是，万一有一天，有人用更好的写法反驳了我，我就可以理直气壮地说，“我不是没给自己打满分么😏”
网友评论