704.二分查找
因为之前有刷过,按照记忆里的做法直接一次就过了。这道题比较基础,唯一需要注意的是一定要用左开右闭和左闭右闭的区间来重新赋值left和right指针,切记不可左右同开,否则会超出时间限制。
附上本题代码如下,采取的是左闭右闭区间的方法。
时间复杂度:O(logn)。
27.移除元素。
思路:因为数组中的元素没有办法直接进行删除,所以只能采取赋值的方式达到删除的效果。本题我采取快慢指针法,分别设立fast和slow两个指针,初始时都指向数组的第一个元素。当指向元素不为待删除元素时,快慢指针同时向后移动;当指向val时,slow不动,而fast向后移动,直到fast指向的元素不再等于val,然后将fast指向元素的值赋给nums[slow],slow和fast再向后移动,直到fast遍历完整个数组。最终slow的值即为移除元素后新数组的长度。
时间复杂度:O(n),虽然是嵌套while,但实际上只有fast遍历一遍了数组。不是所有的嵌套循环时间复杂度都是O(n^2)。
虽然之前已经按照题解做过一次,本次重新写未花费太多时间,但重新写的时候代码块还是有所不同,未能有参考答案简洁,遂又参考进行优化。道阻且长,还需努力加油,希望完成训练营之后的我也能做到代码美观又高效。
本体代码块如下所示。