C++算法练习-day2——27.移除元素
题目来源：. - 力扣（LeetCode）
题目思路分析
给定一个有序数组和一个目标值，题目要求从数组中移除所有等于目标值的元素，并返回移除后数组的新长度。注意，题目要求原地修改数组，即不使用额外的数组空间。
为了解决这个问题，我们可以使用双指针方法。设置一个左指针left，初始指向数组的第一个元素；设置一个右指针right，初始指向数组的最后一个元素。然后，我们进行以下操作：
-
如果左指针指向的元素等于目标值，那么我们需要将其替换为一个不等于目标值的元素。由于数组是有序的，我们可以选择右指针指向的元素（只要右指针还没有遍历完数组）。但是，在替换之前，我们需要检查右指针指向的元素是否也等于目标值。如果等于，我们就将右指针向左移动，直到找到一个不等于目标值的元素。然后，我们将这个元素复制到左指针的位置，并将右指针向左移动一位。
-
如果左指针指向的元素不等于目标值，那么我们就将左指针向右移动一位，继续检查下一个元素。
-
重复上述步骤，直到左指针超过右指针。
最后，左指针的位置就是新数组的长度（因为左指针及其右边的元素都是已经被替换或保留的不等于目标值的元素）。
代码实例及注解
实例：
#include <vector>
class Solution {
public:
int removeElement(std::vector<int>& nums, int val) {
// 初始化左右指针
int left = 0;
int right = nums.size() - 1;
// 当左指针小于等于右指针时，继续遍历数组
while (left <= right) {
// 如果左指针指向的元素等于目标值
if (nums[left] == val) {
// 如果右指针指向的元素不等于目标值，则将其复制到左指针的位置
// 并注意要将右指针向左移动一位
if (nums[right] != val) {
nums[left] = nums[right];
} else {
// 如果右指针指向的元素也等于目标值，则只将右指针向左移动一位
right--;
}
// 由于左指针指向的元素被替换或即将被替换，因此不需要移动左指针
} else {
// 如果左指针指向的元素不等于目标值，则左指针向右移动一位
left++;
}
// 注意：这里不需要显式地移动右指针向左，因为在上面的if语句中已经处理了
// 只有在nums[right] != val的情况下，我们才会执行nums[left] = nums[right]，
// 然后无论是否替换，我们都会在下一次循环迭代中检查right-1或left+1的位置。
}
// 返回新数组的长度，即左指针的位置（因为左指针及其右边的元素都是不等于目标值的）
// 注意：这里返回的是长度，而不是右指针的位置+1（因为右指针可能已经越界或指向了一个被移除的元素）
return left;
}
};
// 注意：上述代码可以进一步优化。实际上，我们不需要每次都检查nums[right] != val，
// 因为即使nums[right] == val，我们也可以通过将right--来跳过它。
// 下面的优化版本省略了这个检查，并简化了代码。
class SolutionOptimized {
public:
int removeElement(std::vector<int>& nums, int val) {
int left = 0;
int right = nums.size() - 1;
while (left <= right) {
if (nums[left] == val) {
nums[left] = nums[right--]; // 直接替换并移动右指针
// 注意：这里不需要再次检查nums[right]（因为即使它等于val，下一次循环也会处理）
// 但是，如果nums[right]原本就不等于val，并且我们将其复制到了nums[left]，
// 那么下一次循环迭代时，left会指向这个新复制的元素（它不等于val），
// 因此我们可以继续向右移动left指针（在else分支中）。
} else {
left++; // 左指针指向的元素不等于目标值，向右移动
}
}
return left; // 返回新数组的长度
}
};注解：
- 在优化版本中，我们省略了对
nums[right] != val的检查，因为即使nums[right]等于val，我们也可以通过将right--来跳过它，并在下一次循环迭代中处理。 - 注意，在替换元素后，我们不需要再次检查被替换的元素（即
nums[left]）是否等于val，因为我们已经用nums[right]的值替换了它，而nums[right]的值是在替换之前就已经确定的。 - 最后返回的是左指针的位置，它表示新数组的长度（因为左指针及其右边的元素都是已经被保留的不等于目标值的元素）。
知识点摘要
- 双指针方法：在处理有序数组或链表时，双指针方法是一种常用的技巧，可以高效地解决问题。
- 原地修改数组：题目要求不使用额外的数组空间，因此我们需要原地修改数组。这通常意味着我们需要通过交换或复制数组中的元素来达到目的。
- 边界条件处理：在处理数组或链表时，需要注意边界条件，如指针是否越界、数组是否为空等。
- 时间复杂度：由于我们使用了双指针方法，并且每个元素最多只被访问一次，因此该算法的时间复杂度为O(n)，其中n是数组的长度。
通过本文的讲解和代码实例，相信读者已经对如何从有序数组中移除特定元素并返回新数组长度有了更深入的理解。
原文地址：https://blog.csdn.net/L613Z/article/details/142830592
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！