【04_移动零】

一、问题

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

请注意 ，必须在不复制数组的情况下原地对数组进行操作。

示例 1:

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

示例 2:

输入: nums = [0]
输出: [0]

二、思路

初始化指针：定义一个指针non_zero_index，它将用于跟踪下一个非零元素应该放置的位置。初始时，这个指针指向数组的起始位置（索引0）。

遍历数组：使用一个循环遍历数组nums中的每个元素。循环的索引变量是i，它从0开始，直到数组的最后一个元素。

检查元素是否为零：在每次迭代中，我们检查当前索引i处的元素是否为0。

交换非零元素：如果当前元素不是0（即nums[i] != 0），我们需要将它移动到数组的前面。为了实现这一点，我们将当前非零元素与non_zero_index指针所指向的元素进行交换。这样，非零元素就被移动到了数组的前面。

更新非零元素位置指针：交换完成后，我们将non_zero_index向前移动一位，以便在下一次迭代中指向下一个应该放置非零元素的位置。

继续遍历：循环继续进行，直到遍历完数组中的所有元素。

结束：当循环结束后，所有非零元素都已经被移动到了数组的前面，而零元素则被留在了后面。

返回结果：最后，函数返回修改后的数组。

三、解法

class Solution:
    def moveZeroes(self, nums: list[int]) -> None:
        left = 0
        right = 0
        for right in range(len(nums)):
            if nums[right] != 0:
                nums[left],nums[right] = nums[right],nums[left]
                left += 1
        return  nums

if __name__ == '__main__':
    nums = [0,1,0,3,5,0,12]
    solution = Solution()
    result = solution.moveZeroes(nums)
    print(result)

四、学习汇总

学习到的：
1、指针是索引维度的，所以，指针left ,可以用nums[left]来表示
2、遍历索引，需要使用range(len(nums))
3、


关于双指针：

双指针是一种常用的算法设计技巧，它利用两个或多个指针来遍历和操作数据结构，尤其是在数组和字符串中。双指针技术可以解决多种问题，如搜索、排序、滑动窗口等。以下是双指针技术的一些基本原理和应用场景：

### 基本原理

1. **遍历**：双指针通常用于遍历数据结构，一个指针从开始位置移动，另一个从结束位置或中间位置移动。

2. **分割**：通过两个指针，可以将数据结构分割成多个部分，分别处理。

3. **比较**：两个指针可以用于比较数据结构中的元素，以找到特定的条件或模式。

4. **更新**：在遍历过程中，可以根据需要更新指针指向的元素。

5. **优化**：双指针可以减少不必要的操作，提高算法的效率。

### 应用场景

1. **查找特定元素**：
   - **两个元素之和**：给定一个数组和一个目标值，找出数组中加起来等于目标值的两个元素的索引。通过一个指针固定一个元素，另一个指针遍历数组找到匹配的元素。

2. **滑动窗口**：
   - **最长子串**：找出一个字符串中不包含重复字符的最长子串。使用两个指针定义窗口的开始和结束，移动结束指针扩展窗口，直到遇到重复字符，然后移动开始指针缩小窗口。

3. **排序**：
   - **归并排序**：使用双指针分别指向已排序数组的起始位置，逐步合并。

4. **搜索旋转排序数组**：
   - **二分查找的变种**：在旋转过的有序数组中查找特定元素，通过比较中间元素与两端点，决定指针如何移动。

5. **链表问题**：
   - **链表相交**：找出两个链表相交的起始节点。使用两个指针分别遍历两个链表，如果链表长度不同，则让较长链表的指针先走，直到两个指针相遇。

6. **循环数组问题**：
   - **循环链表的入口**：使用快慢指针，快指针每次走两步，慢指针每次走一步，如果存在环，则快慢指针会相遇。

7. **矩阵问题**：
   - **搜索矩阵**：在一个有序矩阵中查找一个元素，可以使用双指针从矩阵的左上角开始，根据元素值调整指针位置。

### 实现技巧

- **同步移动**：两个指针同步移动，一个指针固定，另一个根据条件移动。
- **异步移动**：两个指针独立移动，根据各自的条件调整位置。
- **交叉使用**：在某些情况下，两个指针可能会交换角色或位置。

双指针技术的核心在于通过控制指针的移动和位置，有效地解决问题，同时优化算法的性能。

原文地址：https://blog.csdn.net/weixin_42333261/article/details/142553080

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！