前言

最近在复习数据结构与算法，虽然一下子就想到了题目的关键做法：双指针，但是被边界条件硬控太久了，瞄了一眼官方题解，对边界处理比较妙，故反思一下。

题目链接：27. 移除元素

第一次 AC 代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
    public int removeElement(int[] nums, int val) {
            int ans = 0, left = 0, right = nums.length - 1;
            while (left < right) {
                if (nums[left] != val) {
                    ans++;
                    left++;
                } else {
                    while (right > left && nums[right] == val) {
                        right--;
                    }
                    if (right > left) {
                        int temp = nums[left];
                        nums[left] = nums[right];
                        nums[right] = temp;
                    }
                }
            }
        	// nums = [], val = 0
            if (right != -1 && nums[left] != val) {
                ans++;
            }
            return ans;
    }
}

官方题解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
    public int removeElement(int[] nums, int val) {
        int left = 0;
        int right = nums.length;
        while (left < right) {
            if (nums[left] == val) {
                nums[left] = nums[right - 1];
                right--;
            } else {
                left++;
            }
        }
        return left;
    }
}

优化之后 AC 的代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
    public int removeElement(int[] nums, int val) {
            int ans = 0, left = 0, right = nums.length - 1;
            while (left < right) {
                if (nums[left] != val) {
                    ans++;
                    left++;
                } else {
                    nums[left] = nums[right];
                    right--;
                }
            }
            if (right != -1 && nums[left] != val) {
                ans++;
            }
            return ans;
    }
}

优化的部分逻辑具体解释如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
// 优化之前
while (right > left && nums[right] == val) {
    right--;
}
if (right > left) {
    int temp = nums[left];
    nums[left] = nums[right];
    nums[right] = temp;
}

// 优化之后
nums[left] = nums[right];
right--;

// 区别在于不需要保证右指针时刻指向的是等于 val 的数。因为左指针只有在指向不等于 val 的数时才会递增。
// 只要保证右指针在迭代就行了，并且官方指引中也说了并不在乎右边的数据。

官方采用 nums.length 作为右指针可以有效避免一些边界条件，并且在这种情况下 left 就可以代指统计出来的 K，这一步操作也比较妙，不过个人认为这一步改不改问题不大。