LeetCode 283: 移动零

在解决算法问题时，能够清晰地表达思路和解决方案是至关重要的。本文将详细讨论如何解决LeetCode上的一道热门问题——移动零，同时展示如何通过双指针技术高效解决此问题。

image-20240410000633622

问题描述

给定一个数组 nums，编写一个函数将所有 0 移动到它的末尾，同时保持非零元素的相对顺序。

示例

输入: [0,1,0,3,12] 输出: [1,3,12,0,0]

注意：

  • 必须在原数组上操作，不能拷贝额外的数组。
  • 尽量减少操作次数。

思路分析

解决这个问题的关键是如何在遍历数组的同时，有效地将非零元素移至数组前端，而把零移至末尾，且最小化移动次数。这里，我们采用双指针法：

  • 快指针（fast）：遍历数组。
  • 慢指针（slow）：指向当前非零元素应当插入的位置。

通过这种方式，我们能够在一次遍历中解决问题，同时保持代码的简洁性和效率。

代码实现

1
2
3
4
5
6
7
8
9
10
11
void moveZeroes(vector<int>& nums) {
    int slow = 0;
    for (int fast = 0; fast < nums.size(); fast++) {
        if (nums[fast] != 0) {
            if (slow != fast) {
                swap(nums[slow], nums[fast]);
            }
            slow++;
        }
    }
}

复杂度分析

  • 时间复杂度：O(n)，其中 n 是数组长度。我们只需要遍历一次数组。
  • 空间复杂度：O(1)。我们只使用了常数级别的额外空间。

结论

双指针几乎是最常用的算法技巧之一，接下来还有几道双指针的题目，对于如何用好双指针有着更深刻的理解，让我们拭目以待。