LeetCode算 法 实 战 - - - 双 指 针 与 移 除 元 素、快 慢 指 针 与 删 除 有 序 数 组 中 的 重 复 项

💻作 者 简 介：曾 与 你 一 样 迷 茫，现 以 经 验 助 你 入 门 数据 结 构。
💡个 人 主 页：@笑口常开xpr 的 个 人 主 页
📚系 列 专 栏：硬 核 数 据 结 构 与 算 法
✨代 码 趣 语：恰 当 的 数 据 视 图 实 际 上 就 决 定 了 程 序 的 结 构。
💪代 码 千 行，始 于 坚 持，每 日 敲 码，进 阶 编 程 之 路。
📦gitee 链 接：gitee

         在 数 据 结 构 的 世 界 里，每 一 种 设 计 都 可 能 孕 育 出 惊 人 的 效 率 变 革。你 是 否 深 思 过，一 组 精 心 组 织 的 数 据 究 竟 能 创 造 怎 样 的 奇 迹？每 一 次 挖 掘 底 层 原 理，都 是 与 计 算 机 智 慧 的 巅 峰 对 话；每 一 次 剖 析 存 储 模 式，都 在 破 解 数 据 世 界 的 终 极 密 码。准 备 好 迎 接 这 场 盛 宴 了 吗？让 我 们 一 同 探 寻 双 指 针 的 无 尽 奥 秘，见 证 它 如 何 重 塑 数 字 时 代 的 运 行 法 则！

第 一 题 - - - 移 除 元 素

移 除 元 素

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

         假 设 nums 中 不 等 于 val 的 元 素 数 量 为 k，要 通 过 此 题，您 需 要 执 行 以 下 操 作：
1、更 改 nums 数 组，使 nums 的 前 k 个 元 素 包 含 不 等 于 val 的 元 素。nums 的 其 余 元 素 和 nums 的 大 小 并 不 重 要。
2、返 回 k。

示 例 1：
输 入：nums = [3,2,2,3], val = 3
输 出：2, nums = [2,2,,]
解 释：你 的 函 数 函 数 应 该 返 回 k = 2, 并 且 nums 中 的 前 两 个 元 素 均 为 2。
示 例 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 <= nums.length <= 100
0 <= nums[i] <= 50
0 <= val <= 100

方 法 一 - - - 双 重 循 环

思 路 分 析

         题 目 要 求 去 除 一 组 数 中 的 重 复 元 素，并 且 题 目 强 调 nums 的 其 余 元 素 和 nums 的 大 小 并 不 重 要。

         可 以 通 过 双 重 循 环 遍 历 数 组，当 发 现 目 标 值 时，将 其 后 的 所 有 元 素 依 次 前 移 一 位，从 而 覆 盖 掉 目 标 值 元 素。（类 似 顺 序 表 中 的 头 插）这 样 做 的 目 的 是 在 原 数 组 上 直 接 进 行 元 素 移 除 操 作，不 使 用 额 外 的 存 储 空 间，所 以 空 间 复 杂 度 是 O(1)，时 间 复 杂 度 是 O(N^2)。

温 馨 提 示：读 者 们 ，先 自 己 写 代 码，这 是 提 升 编 程 能 力 的 好 机 会。若 未 达 要 求 ，别 气 馁 ，参 考 下 文 解 释 会 有 新 收 获。

下 面 展 示代 码 示 例。

int removeElement(int* nums, int numsSize, int val) 
{int i = 0;int count = 0;int temp1 = numsSize;while (i < temp1) {if (nums[i] == val) {int temp = i;while (temp < numsSize - 1) {nums[temp] = nums[temp + 1];temp++;}count++;temp1--;}else {i++;}}return numsSize - count;
}

注 意

         网 站 上 刷 题 分 为 IO 型 和 接 口 型，IO 型 是 使 用 scanf 得 到 输 入，结 果 使 用 printf，并 且 要 写 出 完 整 程 序。接 口 型 是 结 果 通 过 返 回 值 返 回，只 写 实 现 的 函 数，是 一 部 分 程 序。在 LeetCode 上 刷 题 几 乎 都 是 接 口 型，调 试 起 来 比 较 麻 烦，牛 客 网 中 有 IO 型 和 接 口 型。

以 数 组 元 素 为 3,2,2,3,1,2,4,2 val 为 2 进 行 动 画 演 示。

方 法 二 - - - 双 指 针

双 指 针

         双 指 针 是 一 种 常 用 的 算 法 技 巧，利 用 它 们 之 间 的 相 对 移 动 来 高 效 地 解 决 问 题，核 心 思 想 是 将 遍 历 数 组 和 原 地 修 改 分 离，通 过 一 次 遍 历 完 成 元 素 筛 选 和 数 组 重 构，通 过 指 针 的 位 置 关 系 快 速 定 位 目 标 元 素 或 区 间。时 间 复 杂 度 优 化 至 O(n)。

同 向 双 指 针（快 慢 双 指 针）

         同 向 即 同 一 方 向，两 个 指 针 朝 同 一 方 向 移 动，速 度 可 能 不 同（快 指 针 步 长 更 大，慢 指 针 步 长 较 小）。

思 路 分 析

         题 目 要 求 删 除 数 组 中 等 于 val 的 元 素，因 此 输 出 数 组 的 长 度 一 定 小 于 等 于 输 入 数 组 的 长 度，我 们 可 以 把 输 出 的 数 组 直 接 写 在 输 入 数 组 上。使 用 快 指 针 right 指 向 当 前 将 要 处 理 的 元 素，慢 指 针 left 指 向 下 一 个 将 要 赋 值 的 位 置。

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

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

这 里 以 示 例 1 为 例 进 行 演 示：

温 馨 提 示：读 者 们 ，先 自 己 写 代 码，这 是 提 升 编 程 能 力 的 好 机 会。若 未 达 要 求 ，别 气 馁 ，参 考 下 文 解 释 会 有 新 收 获。

下 面 展 示代 码 示 例。

int removeElement(int* nums, int numsSize, int val) 
{int left = 0;for (int right = 0; right < numsSize; right++) {if (nums[right] != val) {nums[left] = nums[right];left++;}}return left;
}

时 间 复 杂 度：O(N)
空 间 复 杂 度：O(1)

方 法 三 - - - 相 向 双 指 针（面 对 面 移 动）

特 点

         两 个 指 针 分 别 从 数 组 的 两 端 出 发，相 向 移 动。

思 路 分 析

         设 左 指 针 位 于 数 组 的 首 位，右 指 针 位 于 数 组 的 末 尾，向 中 间 移 动 遍 历 该 序 列。如 果 左 指 针 left 指 向 的 元 素 等 于 val，此 时 将 右 指 针 right 指 向 的 元 素 复 制 到 左 指 针 left 的 位 置，然 后 右 指 针 right 左 移 一 位。如 果 赋 值 过 来 的 元 素 恰 好 也 等 于 val，继 续 把 右 指 针 right 指 向 的 元 素 的 值 赋 值 过 来（左 指 针 left 指 向 的 等 于 val 的 元 素 的 位 置 继 续 被 覆 盖），直 到 左 指 针 指 向 的 元 素 的 值 不 等 于 val 为 止。当 左 指 针 left 和 右 指 针 right 重 合 的 时 候，左 右 指 针 遍 历 完 数 组 中 所 有 的 元 素。

这 里 以 示 例 1 为 例 进 行 演 示：

温 馨 提 示：读 者 们 ，先 自 己 写 代 码，这 是 提 升 编 程 能 力 的 好 机 会。若 未 达 要 求 ，别 气 馁 ，参 考 下 文 解 释 会 有 新 收 获。

下 面 展 示代 码 示 例。

int removeElement(int* nums, int numsSize, int val)
{int left = 0, right = numsSize;while (left < right) {if (nums[left] == val) {nums[left] = nums[right - 1];right--;} else {left++;}}return left;
}

时 间 复 杂 度：O(N)
空 间 复 杂 度：O(1)

第 二 题 - - - 删 除 有 序 数 组 中 的 重 复 项

描 述：给 你 一个 非 严 格 递 增 排 列 的 数 组 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。不 需 要 考 虑 数 组 中 超 出 新 长 度 后 面 的 元 素。

方 法 一 - - - 快 慢 指 针

思 路 分 析：题 目 要 求 去 除 数 组 中 的 重 复 元 素，并 且 题 目 强 调 使 数 组 的 前 k 个 元 素 包 含 唯 一 元 素，并 按 照 它 们 最 初 在 nums 中 出 现 的 顺 序 排 列。可 以 使 用 双 指 针 的 快 慢 指 针 求 解 这 个 问 题，慢 指 针 指 向 当 前 唯 一 元 素，快 指 针 遍 历 数 组，发 现 不 同 元 素 时 更 新 慢 指 针。

温 馨 提 示：读 者 们 ，先 自 己 写 代 码，这 是 提 升 编 程 能 力 的 好 机 会。若 未 达 要 求 ，别 气 馁 ，参 考 下 文 解 释 会 有 新 收 获。

下 面 展 示代 码 示 例。

int removeDuplicates(int* nums, int numsSize) 
{int left = 0;         //慢指针:指向当前无重复数组的最后位置int right = left + 1;        //快指针:从第二个元素开始遍历while(right < numsSize)      //遍历整个数组{if(nums[left] == nums[right]){right++;             //遇到重复元素，右移快指针}else{left++;              //找到新元素，更新慢指针位置nums[left] = nums[right]; //将新元素复制到慢指针位置}}return left + 1;  //返回无重复数组的长度（加上第1个元素）
}

空 间 复 杂 度 是 O(1)
时 间 复 杂 度 是 O(N)

方 法 二 - - - 改 进 方 法 一

         相 较 于 方 法 1，方 法 2 对 方 法 1 进 行 了 改 进，改 进 如 下：

边 界 条 件 处 理：
增 加 了 numsSize == 0 的 判 断，避 免 空 数 组 导 致 的 未 定 义 行 为。
指 针 初 始 化 优 化：
left 和 right 均 初 始 化 为 1，因 为 第 一 个 元 素（索 引 0）天 然 无 需 处 理。
比 较 逻 辑 简 化：
通 过 比 较 nums[right-1] 和 nums[right]，直 接 判 断 当 前 元 素 是 否 与 前 一 个 重 复。当 发 现 不 重 复 元 素 时，直 接 赋 值 到 left 位 置，并 递 增 left。

温 馨 提 示：读 者 们 ，先 自 己 写 代 码，这 是 提 升 编 程 能 力 的 好 机 会。若 未 达 要 求 ，别 气 馁 ，参 考 下 文 解 释 会 有 新 收 获。

下 面 展 示代 码 示 例。

int removeDuplicates(int* nums, int numsSize) 
{if(numsSize == 0)           //处理空数组的边界情况{return 0;}int left = 1;               //慢指针:从第二个位置开始写入int right = 1;              //快指针:从第二个位置开始遍历while(right < numsSize)     //遍历整个数组{if(nums[right-1] != nums[right]) //当前元素与前一个不同{nums[left] = nums[right];   //将新元素写入left位置left++;                     //移动left指针}right++;                    //无论如何都移动right指针}return left;                     //返回无重复数组的长度
}

时 间 复 杂 度 是 O(N)
空 间 复 杂 度 是 O(1)

总 结

         至 此，关 于 双 指 针 的 探 索 暂 告 一 段 落，但 你 的 编 程 征 程 才 刚 刚 启 航。编 写 代 码 是 与 计 算 机 逻 辑 深 度 对 话，过 程 中 虽 会 在 结 构 设 计、算 法 实 现 的 困 境 里 挣 扎，但 这 些 磨 砺 加 深 了 对 代 码 逻 辑 和 数 据 组 织 的 理 解。愿 你 合 上 电 脑 后，灵 感 不 断，在 数 据 结 构 的 世 界 里 持 续 深 耕，书 写 属 于 自 己 的 编 程 传 奇，下 一 次 开 启，定 有 全 新 的 精 彩 等 待。小 编 期 待 重 逢，盼 下 次 阅 读 时 见 证 你 们 更 大 的 进 步，共 赴 代 码 之 约！