【面试算法笔记】0102-数组-移除元素 相关
个人主页：https://github.com/zbhgis
前言
本系列主要记录自己学习算法的过程中的感悟。
力扣27.移除元素
链接：https://leetcode.cn/problems/remove-element/description/
注意点
快慢指针做法。
这道题的题目关键在于如何原地操作数组。
1.设计两个指针，一快一慢。
2.当快指针移动至需要保留元素的位置，就将nums[slow]赋值为nums[fast]，同时slow跟着fast继续前进。这样子就能保证slow操作之后，能保留需要的元素。
3.当快指针移动至需要移除元素的位置，就直接跳过进入下一次循环，此时slow还是停留原地，这样子就等于移除了元素。
4.总的来说就是分为保留元素和移除元素这两步，之后如果题目变成了保留元素，那么其实解法就类似
代码
class Solution { public int search(int[] nums, int target) { if (target < nums[0] || target > nums[nums.length - 1]) { return -1; } int left = 0; int right = nums.length - 1; while (left <= right) { int mid = left + (right - left) / 2; if (nums[mid] == target) { return mid; } else if (nums[mid] < target) { left = mid + 1; } else { right = mid - 1; } } return -1; } }时空复杂度分析
fast指针得遍历完整个数组，所以时间复杂度为O(n)
直接在原始数组上修改，空间复杂度为O(1)
力扣26. 删除有序数组中的重复项
链接：https://leetcode.cn/problems/remove-duplicates-from-sorted-array/description/
注意点
快慢指针做法。
这道题的题目关键在于如何原地操作数组。
1.设计两个指针，一快一慢。
2.与上一题类似，不过这一次需要判断是否与前面的元素重复，如果不重复就移动slow，并赋值nums[slow]为nums[fast]，最后返回
3.总的来说就是也是通过指针来保留不重复的值。
代码
class Solution { public int removeDuplicates(int[] nums) { int slow = 0; for (int fast = 0; fast < nums.length; fast ++) { if(nums[fast] != nums[slow]) { slow ++; nums[slow] = nums[fast]; } } return slow + 1; } }时空复杂度分析
同上
力扣283. 移动零
链接：https://leetcode.cn/problems/move-zeroes/description/
注意点
快慢指针做法。
这道题的题目关键在于如何原地操作数组。
1.设计两个指针，一快一慢。
2.与上一题类似，不过这一次需要判断是否为零，不为零的话，就交换nums[fast]和nums[slow]，相当于把零一直往后边送。
代码
class Solution { public void moveZeroes(int[] nums) { int slow = 0; for (int fast = 0; fast < nums.length; fast ++) { if (nums[fast] != 0) { int tmp = nums[fast]; nums[fast] = nums[slow]; nums[slow ++] = tmp; } } } }时空复杂度分析
同上
力扣844. 比较含退格的字符串
链接：https://leetcode.cn/problems/backspace-string-compare/description/
注意点
快慢指针做法。
这道题的题目关键在于如何原地操作数组。
1.设计两个指针，一快一慢。
2.在操作之前，先将字符串转为字符数组才能遍历。
3.与上一题类似，不过这一次fast没碰到退格字符的时候，需要将chars[fast]赋值给chars[slow]，slow一起跟着fast移动。如果碰到退格字符，说明这个字符需要保留，就需要将slow回退一个，相当于删除了一个字符的操作。所以循环结束之后区间[0,slow]相当于实际的数组。
代码
class Solution { public boolean backspaceCompare(String s, String t) { return process(t).equals(process(s)); } private String process(String str) { int slow = 0; char[] chars = str.toCharArray(); for (int fast = 0; fast < chars.length; fast ++) { if (chars[fast] != '#') { chars[slow] = chars[fast]; slow ++; } else { slow = slow > 0 ? -- slow : 0; } } return new String(chars, 0, slow); } }时空复杂度分析
同上