【每日算法Day 15】数组基础1
双指针与删除元素：今天做的这三道关于数组的题目都和数组的访问操作、双指针有关。根据数组中数据的特性与题目的要求，双指针移动的条件和速度不同，有时是同向的，有时是相向的。
# LeetCode 27. 移除元素 (opens new window)
# 题目描述
给你一个数组 nums 和一个值 val，你需要 原地 移除所有数值等于 val 的元素，并返回移除后数组的新长度。 不要使用额外的数组空间，你必须仅使用 O(1) 额外空间并 原地 修改输入数组。 元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。
# 示例
输入：
nums = [0,1,2,2,3,0,4,2], val = 2
输出：
新的长度 5, 并且 nums 中的前五个元素为 0, 1, 3, 0, 4。
2
3
4
# 解题思路
一开始拿到这题就想着使用双指针从数组两边向中间扫描。在左指针小于右指针时，每当左指针扫描到目标数，让右指针扫描到当前往左第一个非目标数的数，就把右指针的值赋值给左指针处，再分别将左右指针往右/左移动一位。
//细节处理有问题的解法，两个指针分别从左右移动
public int removeElement0(int[] nums, int val) {
if(nums==null||nums.length==0) return 0;
int left=0,right=nums.length-1;
while (left <= right) {
//当左指针发现值等于目标值时
if (nums[left] == val) {
//让右指针指向当前从右往左的第一个不等于val的数
while (nums[right] == val) {
right--;
}
//拷贝该数到左指针处并将右指针减一
nums[left]=nums[right];
right--;
}
//无论是否发生了拷贝，左指针都加1是有问题的，例如[3,2,3] 3
left++;
}
return left;
}
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
但是这样的思路在细节处理上是有一些问题的，“让右指针扫描到当前往左第一个非目标数的数”的过程如果数组中全为目标数则会出现right<0的数组下标越界异常，并且while中套while对指针进行操作会让内层循环中的指针不受外层的循环停止条件的限制；返回左指针可能也有问题，因为最后一次赋值后左指针+1，可能该位置是目标数。
为此，可在循环中用条件判断控制单次左指针的移动，并且无需考虑右指针的指向的数字情况。只有在没有发生拷贝（nums[i]不是目标数）时才移动左指针，在发生拷贝时，仅缩小右指针而不改变左指针，表示新数组的长度n减少。把判断拷贝的数是否为目标数的过程移到下一次循环。最终当左指针增长到n-1时，移除过程结束，返回新数组的长度n。
//正确的双指针从左右两侧移动的方法
public int removeElement(int[] nums, int val) {
if (nums==null) return 0;
int i = 0;
int n = nums.length;//右指针应应理解为新数组的长度，规避数组长度为0的情况
while (i < n) {
if (nums[i] == val) {
//不用检查右指针指向数字是否可能是目标数字，因为在下次循环中还会再作检查
nums[i] = nums[n - 1];
//已经知道有一个目标数，则新数组长度减一
n--;
} else {
//nums[i]没问题才会向右移动左指针
i++;
}
}
return n;
}
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
此外，双指针还可以都从数组左侧出发，快指针每次只寻找非目标数的数，依次将快指针指向的内容复制到慢指针处，慢指针每次复制后+1。不过该方法虽然也是O(n)的时间复杂度，能保持元素顺序但和上面的方法相比复制次数会更多。
public int removeElement(int[] nums, int val) {
if (nums==null) return 0;
int slow=0,fast=0;
//可用for精简表达
while(fast<nums.length){
if(nums[fast]==val){
fast++;
}else{
nums[slow]=nums[fast];
slow++;
fast++;
}
}
return slow;
}
2
3
4
5
6
7
8
9
10
11
12
13
14
15
下面这一题中，由于题目特性双指针必须从相邻位置同向出发。
# LeetCode 26. 删除排序数组中的重复项 (opens new window)
# 题目描述
给定一个排序数组，你需要在 原地 删除重复出现的元素，使得每个元素只出现一次，返回移除后数组的新长度。不要使用额外的数组空间，你必须在 原地 修改输入数组 并在使用 O(1) 额外空间的条件下完成。
# 示例
输入：
nums = [0,0,1,1,1,2,2,3,3,4],
输出：
新的长度 5, 且原数组 nums 的前五个元素被修改为 0, 1, 2, 3, 4。
2
3
4
# 解题思路
使用双指针从左侧出发，快指针寻找第一次出现的新数并拷贝到慢指针指向的位置，慢指针表示的是新数组的最后一位，仅在拷贝后+1。
public int removeDuplicates(int[] nums) {
if(nums==null||nums.length==0) return 0;
int slow=0,fast;
for(fast=0;fast<nums.length;fast++){
if(nums[fast]!=nums[slow]){
nums[++slow]=nums[fast];
}
}
return slow+1;
}
2
3
4
5
6
7
8
9
10
下面这一题该26题的基础上加了新的要求：
# LeetCode 80. 删除排序数组中的重复项 II (opens new window)
# 题目描述
给定一个排序数组，你需要在原地删除重复出现的元素，使得每个元素最多出现两次，返回移除后数组的新长度。不要使用额外的数组空间，你必须在原地修改输入数组并在使用 O(1) 额外空间的条件下完成。
# 示例
输入：
nums = [1,1,1,2,2,3],
输出：
新长度 length = 5, 且原数组的前五个元素被修改为 1, 1, 2, 2, 3 。
2
3
4
# 解题思路
26题中快指针寻找的是第一次出现的新数，且慢指针只在需要拷贝时移动1。在26题的基础上，再使用一个变量来保存当前慢指针指向的数字已经出现了几次。
快指针向右移动时
- 如果指向的数字和慢指针指向的数字相同则判断次数：
- 该次数为1，表示fast与slow重合（通常只在开始时slow==fast==0），则不做复制，计数+1，快指针继续向右移动；
- 该次数为2，表示当前快指针指向的数字是第二次出现，则计数+1，将nums[fast]复制到nums[++slow]。
- 该次数大于2，则继续循环，直到nums[fast]和nums[slow]不同，
- 在不同时将nums[fast]复制到nums[++slow]并重置计数为2，表示如果下一次nums[fast]仍等于nums[slow]，则该位置是该数第二次出现。
public int removeDuplicates(int[] nums) {
if(nums==null||nums.length==0) return 0;
int slow=0,fast,times=1;
for(fast=0;fast<nums.length;fast++){
if(nums[fast]==nums[slow]){
switch(times){
case 1:
times++;
break;
case 2:
//复制
times++;
nums[++slow]=nums[fast];
break;
//大于2则继续for循环直到nums[fast]！=nums[slow]
}
}else{
nums[++slow]=nums[fast];
times=2;
}
}
return slow+1;
}
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
另外，看到了一位大神的解法，很巧妙：
public int removeDuplicates(int[] nums) {
if(nums==null) return 0;
int i = 0;
for (int n : nums) {
if (i < 2 || n > nums[i-2]) nums[i++] = n;
}
return i;
}
2
3
4
5
6
7
8
前面的所有方法都是基于比较相邻数字，统计相同数字的出现次数的；而该方法是比较生成的数组倒数第二位和右指针，并不关心某一数字的具体出现次数。
数组的前两个数肯定是满足要求的，对于从nums[2]开始的数字n：
- 如果
n > nums[i-2]不成立（而排序数组中有n>=nums[i-2]），则n一定等于nums[i-2]，进一步推断nums[i-2]、nums[i-1]一定是相同的两个数，当前的nums[i]需要存入下一个大于nums[i-2]的n。 - 如果该式成立，则说明nums[i-2]、nums[i-1]和n三个数中最多只有两个数相同（例如1,1,3或1,2,3或1,3,3），把n复制到nums[i]没有问题。 每次复制完之后i自增，表示新数组的长度，新数组范围是[0,i-1]。