【算法系列-数组】移除元素 (双指针）

【算法系列-数组】移除元素 (双指针)

文章目录

【算法系列-数组】移除元素 (双指针)
- 1. 算法分析🛸
- 2. 删除有序数组中的重复性(LeetCode 26)
- - 2.1 解题思路🎯
  - 2.2 解题过程🎬
  - 2.3 代码举例🌰
- 3. 移动零(LeetCode 283)
- - 3.1 解题思路🎯
  - 3.2 解题过程🎬
  - 3.3 代码举例🌰
- 4. 比较含退格的字符串(LeetCode 844)
- - 4.1 解题思路🎯
  - 4.2 解题过程🎬
  - 4.3 代码举例🌰
- 5. 有效数组的平方(LeetCode 977)
- - 5.1 解题思路🎯
  - 5.2 解题过程🎬
  - 5.3 代码举例🌰

1. 算法分析🛸

移除元素这类题的解题思路在于你能否在数组中找到val(这个val有很多种形式，并不是固定的值)，并将其按照要求进行移除；

最简单的方法就是通过暴力解决，通过多重循环暴力移除，但这样的代码时间复杂度就会高一些；对此，我们可以使用双指针的方式来解决这类问题：
【题目链接】

定义两个指针：

快指针：用来寻找符合新数组要求的元素

慢指针：用来将旧数组中的元素更新为符合新数组要求的元素

通过循环遍历，让fast指针依次遍历整个旧数组，每找到与val不同的元素(即符合新数组要求)，就将这个元素更新到slow指针所在的位置上，然后将slow++，循环结束后slow指针所在位置下标便是整个新数组的数组长度

代码如下：

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

掌握了解题思路后，提供以下几道类型相似的题用来练习：

2. 删除有序数组中的重复性(LeetCode 26)

【题目链接】

2.1 解题思路🎯

双指针

2.2 解题过程🎬

定义两个指针 + 变量val：

快指针：用来寻找未重复出现的元素

慢指针：用来将重复元素更新为未重复出现的元素 val：用来记录最近一次更新的元素 (最开始与数组首元素不一样即可)

通过循环遍历，让fast指针依次遍历整个数组，每找到与val不同的元素，就将这个元素更新到slow指针所在的位置上，然后将slow++，同时更新 val 为原slow位置更新后的元素，循环重复上述过程，循环结束后slow指针所在位置下标便是整个新数组的数组长度

2.3 代码举例🌰

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

3. 移动零(LeetCode 283)

【题目链接】

3.1 解题思路🎯

双指针

3.2 解题过程🎬

通过定义两个双指针将非零元素都移动到最前面，之后从slow指针所在位置开始遍历一遍数组将后面的值都赋零即可

3.3 代码举例🌰

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

4. 比较含退格的字符串(LeetCode 844)

【题目链接】

4.1 解题思路🎯

通过双指针 + 设置变量判断 # 是否被消费来进行字符串元素的删减

4.2 解题过程🎬

这次的指针需要从后面开始遍历，因为 # 退格元素是往左删的

设置快慢指针，变量k用来记录当前未被消费的 # 数量 :

当nums[fast]不等于 # 且k = 0时，更新nums[slow] = nums[fast]，且slow++;
当nums[fast]不等于 # 且k > 0时，k 减 1，slow位置不变，fast继续向前遍历；
当nums[fast]等于 # 时，k 加 1，slow位置不变，fast继续向前遍历；

遍历完数组后，此时slow + 1 位置开始即为字符串经过退格后的正确字符串，返回结果后进行判断即可

4.3 代码举例🌰

class Solution {
    public boolean backspaceCompare(String s, String t) {
        String s1 = removeChar(s);
        String t1 = removeChar(t);
        if (s1.equals(t1)) {
            return true;
        }
        return false;
    }

    public String removeChar(String str) {
        String[] nums = str.split("");
        int slow = nums.length -1;
        int k = 0;
        for (int fast = nums.length - 1;fast >= 0;fast--) {
            if (!nums[fast].equals("#")) {
                if (k == 0) {
                    nums[slow--] = nums[fast];
                    continue;
                }
                k--;
            }
            else {
                k++;
            }
            
        }
        StringBuffer ret = new StringBuffer("");
        for (int i = slow + 1;i < nums.length;i++) {
            ret.append(nums[i]);
        }
        return ret.toString();
    }
}

5. 有效数组的平方(LeetCode 977)

【题目链接】

这道题比较特殊，不再是使用快慢指针的方式来解决问题，而是用左右双指针

5.1 解题思路🎯

这道题为我们提供的数组是一个有序的数组，要求我们将数组中的元素平方之后再进行排序返回在这里插入图片描述

很快能想到使用循环 + 库函数的方式就能暴力解决这道题:

class Solution {
    public int[] sortedSquares(int[] nums) {
        for (int i = 0;i < nums.length;i++) {
            nums[i] = nums[i] * nums[i];
        }
        Arrays.sort(nums);
        return nums;
    }
}

但这样带来的时间复杂度为是O(n + nlogn)，有没有更高效的方法？可以用双指针✅

在这道题中，我们需要抓住一个关键点：

有序数组中元素平方后的最大值一定是由原数组最左边或者最右边的元素的提供的

找到这个关键点后，我们就能通过双指针的方式解决这个问题了

5.2 解题过程🎬

定义左右双指针，并创建一个新的数组ret用来返回结果，定义一个指针cur从新数组的最后开始赋值，进行判断：

当左指针元素的平方值后大于右指针元素的平方值，此时ret[cur] = nums[left] * nums[left]，同时left++, cur–
当右指针元素的平方值后大于左指针元素的平方值，此时ret[cur] = nums[right] * nums[right]，同时right–, cur–

遍历结束后返回赋值后的新数组即可

5.3 代码举例🌰

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