缘起

最近有段时间不敲代码了，昨天一个好兄弟突然跑过来说问我一道面试题，欣然答应之后发现自己一下被问懵了，由此做一下简单记录。关于该问题的博客数目很多，这里只是给一个总结，也算是记录一下自己的心得。

题目

给定一个python的list对象，想要删除其中指定几个下标所在位置的元素，有什么好的解决方案？

e.g.>>> list_given = [1, 2, 3, 4, 5, 6, 7, 8, 9]
>>> index_to_delete = [1, 3, 6]>>> delete_target_index(list_given)
[1, 3, 5, 6, 8, 9]

分析

应该说本题是一个不错的面试题目，能够考察受试者对Python数据结构以及内存分配问题的了解深度。对于给定的一个list，使用python 删除单个元素的方法有很多，最常见方法如下：

使用remove方法
python中list对象的remove方法可以帮我们删除list中出现的某个元素，但是值得注意的是，remove方法只会删除掉该元素在列表中第一次出现的位置，具体使用方法如下：
```
>>> list_given = [1, 4, 3, 3, 2, 2, 3, 5, 7]
>>> list_given.remove(3)
>>> list_given[1, 4, 3, 2, 2, 3, 5, 7]
```
可以看到，remove方法可以用来删除一个列表中已经存在的元素，但是也只能删除其第一次出现位置的该元素。值得注意的是，假如待删除元素不在列表中，调用remove方法会出现ValueError。
如果想删除列表中所有位置的该元素，可以使用如下代码段：
```
>>> list_given = [1, 4, 3, 3, 2, 2, 3, 5, 7]
>>> value_to_delete = 3
>>> while value_to_delete in list_given:list_given.remove(value_to_delete)
>>> list_given[1, 4, 2, 2, 5, 7]
```
可以看到该方法与我们的本意相去甚远，因此排除该方法。
list的pop方法
list这一结构在设计时与栈颇为类似，而其对应的两种方法pop和append与出栈和进栈完全对应，因此在使用时完全可以将其当做堆栈来使用。pop函数在使用时默认也是不需要参数的，直接弹出当前栈顶元素。当然，list在设计时也并非就是堆栈，因此其有insert方法可以直接在对应下标处插入元素，pop方法也可以带参数使用，从而删除指定下标处的元素。回头看我们当前的问题，一种很常见的思路便出现了：
```
>>> list_given = [1, 4, 3, 3, 2, 2, 3, 5, 7]
>>> index_to_delete = [1, 3, 6]
>>> for index in index_to_delete:list_given.pop(index)
>>> list_given[1, 3, 3, 2, 3, 5]
```
好家伙不仔细看你肯定觉得自己写的没啥问题，这不是都给删除掉了？可是定睛一看才发现，问题并没有那么简单。元素5前面的3理应被我删除掉了，它咋阴魂不散呢？这就是很多时候出现问题的地方，python中list是一个动态分配内存空间的对象，因此当你删除了前面元素的时候，后面元素的索引其实已经变掉了，因此你删除的位置在新的list中其实已经发生了改变，这一点可以在内存分配中观察到：

上图为删除元素之前各个元素的索引结果，下面我们单步执行程序，删除掉第一个被要求删除的位置的元素之后效果如图：

可以看到，下标为1位置的元素4已经飞升了，但是与此同时，列表中其余元素的下标也都对应发生了变化，原列表中的索引与新列表已然不同，假如继续使用上述for循环来解决该问题，就会导致错误的删除元素，从而导致新列表与期望结果不一致。
使用delete方法删除
删除元素的效果与pop方法类似，当然存在的问题也就是类似的，这里不再赘述。

可以看到，以上几种方法均不能很好地解决我们所提出的问题，那么究竟该如何解决这一问题呢？下面给出几种比较优质的思路供大家伙参考。

动态修改待删除的下标
敌动我不动的被动打法显然不适合这一问题，因此一种解决方法就是动态修改待删除的下标，这叫随机应变。博主之前其实遇到过这个问题，但是一开始被问上的时候确是一下子没想到，因此面试的心态还是相当重要的，更何况我面对的还不是面试官…，太菜了！
```
list_given = [1, 2, 3, 4, 5, 6, 7, 8, 9]
index_to_delete = [1, 3, 6]
counter = 0for index in index_to_delete:index = index - counterlist_given.pop(index)counter += 1
>>> list_given[1, 3, 5, 6, 8, 9]
```
可以看到此时删除之后的列表与我们问题所描述的要求就完全一致了。

使用python自带的counter
这一解法来自@Skaldak，就是面试官本官。利用python的enumerate方法我们就自行找到了counter。

list_given = [1, 2, 3, 4, 5, 6, 7, 8, 9]
index_to_delete = [1, 3, 6]for counter, index in enumerate(index_to_delete):index = index - counterlist_given.pop(index)

到这里我们就给出了两种很基本的操作方法，这也是python中很常见的操作。但是，问题的本质并没有被发掘出来，那就是下标变化这一问题。下标为什么会变化呢？原因很简单，我们移除了前面的某个元素，其后各个元素的下标自然就发生了变化。那么问题来了，如何不让下标发生变化？其实也很简单，每次我们移除元素的时候，被移除元素之前的所有元素的下标是不会发生变化的，那么思路是不是就有了呢？

逆序遍历法删除元素
```
list_given = [1, 2, 3, 4, 5, 6, 7, 8, 9]
index_to_delete = [1, 3, 6]for index in reversed(index_to_delete):list_given.pop(index)
```
该方法的有效性在待删除下标数组有序时是不证自明的。在待删除下标数组无序时，需要先进行排序操作（可以考虑直接降序排列，这样子省去了reverse的操作）。

综上所述，很直接的三种方法已经给出来了。可以看到，以上三种操作均基于原始list进行删除，在空间效率上应该说是相当高的。下面介绍的两种方法是牺牲空间复杂度的操作，但是这种曲线救国的思想还是值得借鉴的。

利用列表生成式直接构建新list，上码：
```
list_given = [1, 2, 3, 4, 5, 6, 7, 8, 9]
index_to_delete = [1, 3, 6]new_list = [list_given[i] for i in range(len(list_given)) if i not in index_to_delete]
```
按照python的特性，这种方式的执行效率可以说是相当高的（列表生成式是python内置的构建方法，执行时间不必多说，懂的都懂：)）
利用dict作为中间结构解决上述问题
目前，我们所遇到的主要问题就是下标的变动问题，那么我们是否可以选择一种无序结构作为中间变量来完成我们删除元素这一任务呢？答案是肯定的，python提供的dict类型可以帮助我们解决这一问题：
```
list_given = [1, 2, 3, 4, 5, 6, 7, 8, 9]
index_to_delete = [1, 3, 6]my_dict = {}
for index, value in enumerate(list_given):my_dict[index] = valuefor index in index_to_delete:my_dict.pop(index)result = list(my_dict.values())
```
这一解决方法本质上与上述新建list的方法没有本质区别，这里只是提供一种思路。