当前位置：首页 > news >正文

每日两道力扣，day5

news 2026/8/5 6:14:24

每日两道力扣，day5

每日两道力扣，今日是：

27. 移除元素 - 力扣（LeetCode）

283. 移动零 - 力扣（LeetCode）

第一题：移除元素

27. 移除元素 - 力扣（LeetCode）

1.思路：

这是代码随想录上的一道双指针算法模板题。

（1）我们先尝试暴力的方法，利用两个for循环，我们可以很好地解决这个题目。第一个for循环，用来控制数组的左端的变化，第二个for循环用来通过遍历去移除元素。只要第一个循环里的nusm[i] == val，咱们就在第二个循环里移除元素。时间复杂度O(n^2)，尽管能跑过，但显然不是最优解。

（2）为了探寻最优解，我们将引入双指针算法。这将是我们算法旅程中的好伙伴，在数组，链表，栈等等情景里面，都常常会有他的身影。暴力法运用了两个for循环，那我们可以通过双指针降维打击，只采用一个for循环解决问题。首先初始化两个指针，slow，fast为0。快指针fast先跑，用来查找数组里面值不为val的元素，找到后，利用slow和fast更新数组，循环结束后，返回的slow的大小，就是题目的解。时间复杂度为O(n)。

2.代码实现：

（1）方法一：（暴力）

class Solution { public: int removeElement(vector<int>& nums, int val) { int n = nums.size(); for(int i = 0; i < n; i++) { if(nums[i] == val) { for(int j = i + 1; j < n; j++) { nums[j - 1] = nums[j]; } //因为此时，下标i以后的元素都往前移动了一位，为了确保不发生遗漏的情况，i也得往前移动一位 i--; //移除了一个元素，数组大小减1 n--; } } return n; } };

（2）方法二：(双指针)

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

3.细节

这个题比较简单，没有什么细节可注意的。

第二题：移动零

283. 移动零 - 力扣（LeetCode）

1.思路：

这道题是一道典型的双指针模板题。我们可以想移除元素那样采用快慢指针，其中快指针fast用来寻找不为0的元素。找到后利用swap交换nums[slow]，nums[fast]。

2.代码实现：

class Solution { public: void moveZeroes(vector<int>& nums) { int slow = 0, n = nums.size(); for(int fast = 0; fast < n; fast++) { if(nums[fast] != 0) { swap(nums[slow], nums[fast]); slow++; } } } };

3.细节：

尽管写出来了，但我们看到题目的进阶提问 **进阶：**你能尽量减少完成的操作次数吗？不免疑惑，我们使用双指针算法已经很完美了，还有哪里可以优化的地方呢？如果面试官在算法面问道你这个问题时，你该怎么办？

破案：当前代码在哪里浪费了操作次数？

在 C++ 中，一次swap(a, b)函数的底层运行其实包含了3 次赋值操作：

int temp = a;
a = b;
b = temp;

现在想象一个极端的测试用例：数组里根本没有 0，比如[1, 2, 3, 4, 5]。你的代码会怎么跑？

fast遇到1，非零。执行swap(nums[0], nums[0])。自己和自己交换（白白浪费 3 次赋值）。
fast遇到2，非零。执行swap(nums[1], nums[1])。（又浪费 3 次赋值）。
…

如果数组有 10000 个非零元素，你的代码就会做30000 次没有意义的自我赋值操作！

为了解决这个问题，我们有两种优化方向。

第一种：打个补丁

既然问题出在“自己和自己交换”上，那我们加个判断：只有当fast和slow不在同一个位置时，才进行交换。

class Solution { public: void moveZeroes(vector<int>& nums) { int slow = 0, n = nums.size(); for(int fast = 0; fast < n; fast++) { if(nums[fast] != 0) { // 优化点：如果不重合才交换，避免全是非0元素时的自我交换 if (slow != fast) { swap(nums[slow], nums[fast]); } slow++; } } } };

效果：遇到[1, 2, 3, 4, 5]这样的纯非零数组时，操作次数直接降为0 次交换。

第二种：“覆盖 + 填坑” 法

swap始终太贵了（3 次赋值）。如果不追求“实时把 0 换到后面”，我们可以采取**“两步走”**的策略：

第一步（覆盖）：只管把非 0 的数字一股脑儿往前面扔。遇到非 0 的，直接覆盖到slow的位置。单次覆盖只需1 次赋值！第二步（填坑）：当前面都被非 0 数字占满后，slow往后的位置本来应该都是 0。我们直接写个循环，把后面的全填成 0 就行了。

class Solution { public: void moveZeroes(vector<int>& nums) { int slow = 0, n = nums.size(); // 步骤 1：把所有非 0 元素统统往前覆盖 for (int fast = 0; fast < n; fast++) { if (nums[fast] != 0) { // 直接覆盖，不用 swap。只需 1 次赋值操作！ nums[slow] = nums[fast]; slow++; } } // 步骤 2：此时所有的非 0 元素都已经按顺序排在前面了 // slow 指向的及后面的位置，全该是 0，我们自己手动填平 for (int i = slow; i < n; i++) { nums[i] = 0; } } };

为什么方案 2 更好？（算一笔账）

假设数组是[1, 2, 3, 4, 0]（大部分是非零元素）：