数组的移除

大家好，欢迎来到IT知识分享网。

1.暴力解法

这个其实就是课上的写法 用两层for循环去嵌套

时间复杂度 O（n^2）

空间复杂度O（1）

class solution{ public int removeElement(int[] nums,int val){ int size = nums[size]; for(int i = 0;i<nums.length;i++){ if(nums[i] == val){ for(int j = i+1;j<nums.size;j++){ nums[j-1] = nums[j]; } i--; //因为此时i后面的那个元素i+1 跑到了i的位置 //如果没有这个当执行完后已经是i+1了就跳过了原来在i+1位置但是现在在i位置的那个元素 //所以我们要让i--；这样子i++之后就又跑回了i的位置 就不会有遗漏了 size--; } } return size; } }

2.快慢指针法

我们可以借助两个指针 一个是fast快指针 一个是slow慢指针

如下图 我们的的快指针只把不是我们要删除的元素 赋值到slow

根据这个思路 我们就可以写出代码

class solution{ public int removeElement(int[] nums,int val){ int slow = 0; for(int fast = 0;fast<nums.length;i++){ if(nums[fast]!=val){ //也就是我们上面说的只有不等于的我们要删除的值的时候 //才可以赋值 然后赋值完了 当然要让slow++ ；没有赋值就一直等着 就不用++呀 nums[slow] = nums[fast]; slow++; } } return slow; } }

26. 删除有序数组中的重复项 – 力扣（LeetCode）

所以我们就可以对这题目进行解析：

也是定义一下快慢指针 但是有所不同的是它要删除的值 一直在改变 如果有重复 那就删除掉

因为nums[0]肯定可以放心写下去  并且让nums[0] 作为不能重复的第一个元素出现

所以val=nums[0]

所以我们从nums[1]开始 如果val== nums[1]

那么就说明 它是我们不要的重复元素 所以不可以把它赋值给慢指针所在的位置

所以fast要继续++；

直到找到是我们要的不重复元素

如果val！=nums[1]

那么就说明 它是我们要的不重复元素 所以就可以把它赋值给慢指针所在的位置

所以slow也可以++；

而且这个时候val就得改变了 因为题目也有说 数组是递增数组 所以val的新值应该是我们刚才赋值给慢指针的值。

class Solution { public int removeDuplicates(int[] nums) { int val = nums[0]; int slow = 1; int fast; for(fast = 1;fast<nums.length;fast++) { if(nums[fast]!=val) { nums[slow] = nums[fast]; slow++; val = nums[fast]; } } return slow; } }

283. 移动零 – 力扣（LeetCode）

所以我们对这题解析 ：

我们可以知道把不等于0的数前移 其实就是把是0的元素删除

但是呢它得在最后把0加回去 我们就得知道一个性质

慢指针 最后的大小 会是现在数组的大小 但是我们知道数组是从0开始的

也就是0-slow-1是现在不是0的那些元素 

所以我们就可以直接nums[slow] 开始赋值 0.

class Solution { public void moveZeroes(int[] nums) { int slow = 0; int size = 0; for(int fast = 0;fast<nums.length;fast++) { if(nums[fast]!=0) { nums[slow] = nums[fast]; slow++; } if(nums[fast] == 0) { size++; } } while(size!=0) { nums[slow] = 0; slow++; size--; } } }

844. 比较含退格的字符串 – 力扣（LeetCode）

所以我们对这题解析 ：

它的意思是遇到了#需要把#前面的消除掉 

那么其实我们就可以认为它也是用双指针删除

但是遇到# 不是删除#号所在位置的 而是#号的钱一个位置

但是我们又要防止数组越界

如果第一个就是#号 那么我们就让slow等于0就好了

class Solution { public boolean backspaceCompare(String s, String t) { s = txtEditor(s); t = txtEditor(t); return Objects.equals(s, t); } public String txtEditor(String s) { char[] chars = s.toCharArray(); int length = chars.length; int slow = 0; for (int fast = 0; fast < length; fast++) { if (chars[fast] == '#') { slow = slow == 0 ? 0 : slow - 1; } else { chars[slow] = chars[fast]; slow++; } } return new String(chars).substring(0, slow); } }

 977. 有序数组的平方 – 力扣（LeetCode）

所以我们对这题解析 ：

因为 最大的肯定在两边 因为这是个非递减函数 

那么我们就令创建两个指针 left和right 相比较哪边的更大 

大的赋值进行 当left超过right的时候就算遍历完了一个数组

class Solution { public int[] sortedSquares(int[] nums) { int[] p = new int[nums.length]; int right = nums.length-1; int m = right; int left = 0; while(left<=right) { if(nums[right]*nums[right]>=nums[left]*nums[left]) { p[m] = nums[right]*nums[right]; right--; m--; } else { p[m] = nums[left]*nums[left]; left++; m--; } } return p; } }

总结一下 就是双指针可以让时间复杂度降低很多 但是双指针不止包括 快慢 也包括相向 所以我们需要灵活变通。