LeetCode 27.移除元素

题目描述

给你一个数组 nums 和一个值 val，你需要 原地 移除所有数值等于 val 的元素。元素的顺序可能发生改变。然后返回 nums 中与 val 不同的元素的数量。

假设 nums 中不等于 val 的元素数量为 k，要通过此题，您需要执行以下操作：

  • 更改 nums 数组，使 nums 的前 k 个元素包含不等于 val 的元素。nums 的其余元素和 nums 的大小并不重要。
  • 返回 k。

示例 1:

输入: nums = [3,2,2,3], val = 3
输出: 2，nums = [2,2,_,_]
解释: 你的函数函数应该返回 k = 2, 并且 nums 中的前两个元素均为 2。你在返回的 k 个元素之外留下了什么并不重要（因此它们并不计入评测）。

示例 2:

输入: nums = [0,1,2,2,3,0,4,2], val = 2
输出: 5，nums = [0,1,4,0,3,_,_,_]
解释: 你的函数应该返回 k = 5，并且 nums 中的前五个元素为 0,0,1,3,4。注意这五个元素可以任意顺序返回。

提示：

  • $0 \le {nums.length} \le 100$
  • $0 \le {nums[i]} \le 50$
  • $0 \le {val} \le 100$

思路

题目要求删除数组中等于 val 的元素，因此输出数组的长度一定小于等于输入数组的长度，我们可以把输出的数组直接写在输入数组上。数组的元素在内存地址中是连续的，不能单独删除数组中的某个元素，只能覆盖。

最容易想到的就是暴力解法，使用两个 for 循环，第一个 for 循环遍历数组元素 ，第二个 for 循环更新数组。

可以使用双指针进行优化：使用快指针和慢指针在一个 for 循环下完成两个 for 循环的工作

快慢指针的定义：

  • 快指针：指向当前需要处理的元素
  • 慢指针：指向下一个将要赋值的位置

如果快指针指向的元素不等于 val ，它一定是输出数组的一个元素，就将快指针指向的元素复制到慢指针的位置，快慢指针同时后移。

如果快指针指向的元素等于 val ，它不能在输出数组里，此时慢指针不动，快指针右移一位。

整个过程保持不变的性质是：区间 [0, slow) 中的元素都不等于 val。

当快指针遍历完输入数组以后，slow 的值就是输出数组的长度。

二分查找

C++代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    int removeElement(vector<int>& nums, int val) {
        int slow = 0, fast = 0;
        while (fast < nums.size()) {
            if (nums[fast] != val) {
                // 当前要处理的元素的值不等于 val, 将其保存到新数组中（放到原数组slow的位置）
                swap(nums[slow], nums[fast]);
                // 此时 slow 后移，指向下一个可以赋值的位置，保证 [0, slow)区间的元素一定不等于 val
                ++slow;
            }
            ++fast;
        }
        return slow;
    }
};
  • 时间复杂度：O(n)
  • 空间复杂度：O(1)

LeetCode 26.删除有序数组中的重复项

题目描述

给你一个 非严格递增排列 的数组 nums ，请你原地删除重复出现的元素，使每个元素 只出现一次 ，返回删除后数组的新长度。元素的 相对顺序 应该保持 一致 。然后返回 nums 中唯一元素的个数。

考虑 nums 的唯一元素的数量为 k ，你需要做以下事情确保你的题解可以被通过：

  • 更改数组 nums ，使 nums 的前 k 个元素包含唯一元素，并按照它们最初在 nums 中出现的顺序排列。nums 的其余元素与 nums 的大小不重要。
  • 返回 k 。

示例 1:

输入: nums = [1,1,2]
输出: 2，nums = [1,2,_]
解释: 函数应该返回新的长度 2 ，并且原数组 nums 的前两个元素被修改为 1, 2 。不需要考虑数组中超出新长度后面的元素。

示例 2:

输入: nums = [0,0,1,1,1,2,2,3,3,4]
输出: 5，nums = [0,1,2,3,4]
解释: 函数应该返回新的长度 5 ， 并且原数组 nums 的前五个元素被修改为 0，1，2，3，4。不需要考虑数组中超出新长度后面的元素。

提示：

  • $1 \le {nums.length} \le 3*10^{4}$
  • $-10^4 \le {nums[i]} \le 10^4$
  • $nums$ 已按 非严格递增 排列

思路

nums 已按 非严格递增 排列，说明重复元素一定是彼此相邻的，只需要保留一个即可。那么我们可以理解为每个非空数组的第一个元素一定的需要保留的，可以考虑一种极端情况 nums = [1,1,1,1,1] ，只需要保留数组中第一个即可。

同样可以使用双指针，只需要遍历一边数组即可：

  • 快指针：指向当前需要处理的元素
  • 慢指针：指向已经处理好的非重复元素的最后一个，这里与上一题有所不同，这里的有效区间是 [0, slow] ,这里是闭区间，所以最后需要返回的是 slow + 1

如果快指针指向的元素不等于慢指针指向的元素 ，它一定是输出数组的一个元素，就将快指针指向的元素复制到慢指针的后一个位置，快慢指针同时后移。

如果快指针指向的元素等于慢指针指向的元素，说明该元素重复了，慢指针不动，快指针右移一位。

整个过程保持不变的性质是：区间 [0, slow] 中的元素都不重复。

当快指针遍历完输入数组以后，slow + 1 的值就是输出数组的长度。

C++代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    int removeDuplicates(vector<int>& nums) {
        int slow = 0, fast = 1;
        while (fast < nums.size()) {
            if (nums[slow] != nums[fast]) {
                // 当前要处理的元素的值不等于 val, 将其保存到新数组中（放到原数组slow + 1的位置）
                nums[slow + 1] = nums[fast];
                // 此时 slow 后移，指向新数组的末尾，保证 [0, slow] 区间的元素一定不等于 val
                ++slow;
            }
            ++fast;
        }
        return slow + 1;
    }
};
  • 时间复杂度：O(n)
  • 空间复杂度：O(1)