"删除排序数组中的重复项" python + Jupyter lab IDE

题目:

给定一个排序数组，你需要在 原地 删除重复出现的元素，使得每个元素只出现一次，返回移除后数组的新长度。不要使用额外的数组空间，你必须在 原地 修改输入数组 并在使用 O(1) 额外空间的条件下完成。

示例 1:

给定数组 nums = [1,1,2],

函数应该返回新的长度 2, 并且原数组 nums 的前两个元素被修改为 1, 2。

你不需要考虑数组中超出新长度后面的元素。

示例 2:

给定 nums = [0,0,1,1,1,2,2,3,3,4],

函数应该返回新的长度 5, 并且原数组 nums 的前五个元素被修改为 0, 1, 2, 3, 4。

你不需要考虑数组中超出新长度后面的元素。

---

解题思路 :

by JiaJia

1. 满足空间复杂度 o(1), 不允许额外的分配数组空间,所以需要在原来的列表基础上修改元素

2. 题目针对排序数组,首先可设置一个step, 从0 开始, 该step既是数组index的初始位置, 也是遍历整个数组元素后,每比较两两元素值不同时, 该step自增1, 往前走一步. 直至走完整个数组. 增加的步数即为去重后的数组长度.

3. 时间复杂度 o(n), 因为遍历整个数组一次即可

解法 一 :

解一

测试结果:

解一运行结果

解法二:

第一种方法可以很方便求出数组去重后的长度.

如果需要返回新数组元素,则可以从尾部开始,从后往前倒序遍历,遇到重复元素,用pop弹栈弹出该元素

代码实现：

解二

测试结果: 

方法2运行结果

解法二 思考题1: 

为什么遍历数组采用的倒序,从后往前呢?若for循环里面,正序方向遍历,结果会怎样呢?

解法二 思考题2:

for i in range (len(nums))[::-1]  区别于

for i in range (len(nums)-1, 0, -1) 二者区别在哪里呢?

解法二 思考题1 回答:

正序 for 循环的时候,pop 一个位置元素(该元素可能是(0,len)之间任意位置), 如此一来,正序会打乱掉index的位置,当下一次i+1 遍历的时候,原有元素的index位置会有变化调整. 比如 index [0,1,2,3,4,5], pop(index[2]), 那么原有 index[3]这个位置,将变成下一次遍历index[2]的位置,相当于后续数组元素整体前移.

而倒序for循环的时候, pop之后,下一次遍历,是从后往前进行的, 所以剩余数组中元素的index位置值不会产生变化. 比如, index [0,1,2,3,4,5] 这样位置, 从后往前遍历从5开始, pop(index[4]), 把位置4元素弹出.那么接下来遍历的index 依旧是 index[0,1,2,3]

解法二 思考题2 回答:

range (len(nums))[::-1], index 位置是从 len(nums)-1 到 0

range (len(nums)-1, 0, -1), index 位置是从 len(nums)-1 到 1 (中间位置0 ,开区间,不含0)

所以,倒排序比较位置是i 和 i-1, 显然用[::-1]不可取,需要调整成 range (len(nums))[:0:-1],

解法三:

另外一种方法可以使用,while正序循环遍历, 加上del / remove 列表元素,删除重复元素

如果相邻元素相等移除,否则位置自加1, 比较下一对

代码实现:

解法三

测试结果：

解法三运行结果

解法三 思考题1:

解法二和解法三,都是通过pop, remove, del更新了数组元素, 每次更新势必影响了数组的index. 原有元素,未必在原来的位置上,可能产生了位置前移

为何解法三, 可以通过正序循环while 来实现解体思路,而不是倒序循环呢?

解法三 思考题1 回答:

首先, 数组的增删改,都会改变原有元素的下标位置,发生部分元素的位置前后移.

其次, 解法三, while正序循环,退出机制是遍历到数组长度最后一个位置, while不涉及index的自增,自减. 需要我们定义下标位置从0开始

然后, 通过下标 i 来控制整个遍历的先后顺序. 当有重复值的时候, 仅删除. i 不变. 而当, 近邻两个元素值不同时, i自增,进入下一次遍历.

对于, 解法二, 用for循环控制遍历, 每一次遍历都会发生 i+1 (自增)以便进入下一次遍历. 所以执行完pop()弹栈时,若i自增,对于正序遍历, 会漏掉一些元素位置. 而倒序从后往前遍历, 从尾部弹走一个元素, i++,不会改变剩余元素在数组中的下标位置