给定一个长度为n的整型数组，请设计一个尽可能高效的算法，删除该数组中所有值为K的元素。用C++实现

为了高效地删除给定数组中所有值为K的元素，可以采用双指针策略，即使用两个指针i和j，分别表示当前未处理的位置和已移除元素的位置。遍历数组，当遇到值不为K的元素时，将其移动到新位置i，并将i和j向后移动一位。遍历结束后，数组中剩余的就是去掉K的子序列。

以下是C++的实现：

#include <vector>

void removeElement(std::vector<int>& nums, int k) {
    int i = 0; // 未处理的元素指针
    for (int j = 0; j < nums.size(); ++j) { // 遍历整个数组
        if (nums[j] != k) { // 如果元素不是k
            nums[i++] = nums[j]; // 将元素移到未处理区域并更新指针
        }
    }
    // 裁剪多余的空间
    nums.resize(i);
}

这个算法的时间复杂度是O(n)，因为它只遍历了一次数组。空间复杂度是O(1)，因为我们只在原地修改了数组，没有额外的存储需求。

相关问题

给定一个长度为n的整型数组，请设计一个尽可能高效的算法，删除该数组中所有值为K的元素。

给定一个整数数组 `arr` 和一个整数 `k`，可以设计一个线性时间复杂度的算法来删除数组中所有值为 `k` 的元素。这个算法叫做“双指针法”或“快慢指针”，步骤如下：

1. 初始化两个指针，一个 `slow` 指针用于记录当前位置，一个 `fast` 指针用于跳过值为 `k` 的元素。
2. 遍历数组：
- 如果当前元素不是 `k`，将 `slow` 向前移动一位，并把下一个元素赋值给 `slow` 的位置，保持数组有序。
- 如果当前元素是 `k`，只移动 `fast` 指针，跳过它。
3. 当遍历完整个数组后，`arr[slow...arr.length]` 就是一个去除了值为 `k` 元素的新数组。

Python 代码示例：

def removeElement(arr, k):
    slow = 0
    for fast in range(len(arr)):
        if arr[fast] != k:
            arr[slow] = arr[fast]
            slow += 1
    return arr[:slow]