27. Remove Element

移除元素:给定一个数组和一个值,移除数组中该值出现的所有实例,最终返回移除后的新的数组长度。

要求不能分配额外的数组空间,空间复杂度是常量级的,原数组中的元素顺序是可变的,超出长度的部分的值无关紧要

27. Remove Element

我的第一个想法是移动数组元素,也就是把数组中与该值相等的元素统统往后移,利用两个for循环即可实现,但是这样的话时间复杂度是O(n2),确实比较慢。

27. Remove Element

提交结果如图所示:

27. Remove Element

于是思考改进速度的方法。换个角度思考,移除数组中与给定值相等的所有实例,其实不就是统计与该值不等的数的个数吗,于是第二种方法出炉,并且这种方法的时间复杂度是O(n)的

27. Remove Element

很奇怪,提交结果跟之前是一样的,从此以后再也不相信提交结果了。。。

27. Remove Element