Python蓝桥杯训练：基本数据结构 [数组]——双指针法

文章目录

• Python蓝桥杯训练：基本数据结构 [数组]——双指针法
• • 一、力扣上面一些关于数组的题目练习
  • • 1、双指针法

本次博客我是通过Notion软件写的，转md文件可能不太美观，大家可以去我的原笔记中查看：Python蓝桥杯训练：基本数据结构 [数组]，持续更新中，另外这是我创建的编程学习小组频道，想一起学习的朋友可以一起！！！

一、力扣上面一些关于数组的题目练习

1、双指针法

双指针法介绍：
双指针法（Two Pointers）是一种在数组或链表等数据结构中移动两个指针来查找或遍历特定元素的算法。两个指针分别从首尾开始遍历，根据题目要求不断移动指针来缩小查找范围。
双指针法常用于解决数组或链表中的滑动窗口问题、快慢指针问题、双指针问题等。其时间复杂度通常为O(n)，空间复杂度为O(1)。
双指针法常见应用场景如：

• 双指针法可以很好地解决链表中的快慢指针问题，如找到链表中间节点或倒数第 k 个节点。
• 双指针法可以很好地解决数组中的滑动窗口问题，如在数组中找到最大/小子数组、最长不重复子串等。
• 双指针法可以很好地解决回文字符串问题。

• 题目一：[移除元素](https://leetcode.cn/problems/remove-element/)

📖 给你一个数组 nums 和一个值 val，你需要 原地 移除所有数值等于 val 的元素，并返回移除后数组的新长度。

不要使用额外的数组空间，你必须仅使用 O(1) 额外空间并 原地 修改输入数组。

元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。

示例1：

输入：nums = [3,2,2,3], val = 3
输出：2, nums = [2,2]
解释：函数应该返回新的长度 2, 并且 nums 中的前两个元素均为 2。你不需要考虑数组中超出新长度后面的元素。例如，函数返回的新长度为 2 ，而 nums = [2,2,3,3] 或 nums = [2,2,0,0]，也会被视作正确答案。

示例2：

输入：nums = [0,1,2,2,3,0,4,2], val = 2
输出：5, nums = [0,1,4,0,3]
解释：函数应该返回新的长度 5, 并且 nums 中的前五个元素为 0, 1, 3, 0, 4。注意这五个元素可为任意顺序。你不需要考虑数组中超出新长度后面的元素。

提示：

0 <= nums.length <= 100
0 <= nums[i] <= 50
0 <= val <= 100

---

🤔 这道题考察的是双指针的方法，我们可以通过双指针法而不用进行删除操作解决移除数组中指定元素的问题，具体思路如下：给你一个数组

首先定义两个快慢指针，一个指针 fast 指向当前遍历到的位置，另一个指针 slow 指向新数组的尾部，初始化 fast 和 slow 指针都为0，意思是开始都指向索引为0的位置，定义一个变量size为nums的长度，然后使用while循环进行判断当 fast 指针没有遍历完整个数组时，比对当前的nums[fast] 和 val

• 如果不等于，把当前的nums[fast] 移动到nums[slow], 并且把 slow 向后移动一位
• 如果相等，则不做任何操作
• fast 指针每次遍历结束时，指针向后移动一位

最后 return slow, 返回新数组的长度
这样我们就在原地移除了所有数值等于 val 的元素，时间复杂度为 O(n)，空间复杂度为 O(1)。

---

✍🏻 代码实现：

class Solution:def removeElement(self, nums, val):fast, slow = 0, 0size = len(nums)while fast < size:if nums[fast] != val:nums[slow] = nums[fast]slow += 1fast += 1return slow

也可以这样写：

class Solution:def removeElement(self, nums, val):if not nums:return 0slow = 0for fast in range(len(nums)):if nums[fast] != val:nums[slow] = nums[fast]slow += 1return slow

B站上面卡尔老师对于这道题的思路讲得很不错，在这里推荐大家去看看他的教学视频：

https://www.bilibili.com/video/BV12A4y1Z7LP/?spm_id_from=333.1007.top_right_bar_window_history.content.click&vd_source=eae0406d86828f39f6ac3a3b0e8a2a34

---

• 题目二：[移动零](https://leetcode.cn/problems/move-zeroes/)

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

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

示例1：

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

示例2：

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

提示：

1 <= nums.length <= 104
-231 <= nums[i] <= 231 - 1

---

🤔 本题有个专门的要求：必须在不复制数组的情况下原地对数组进行操作，所以我们可以联想到使用双指针法进行替换操作，上一个题我们是删除元素，将要删除的元素移动到数组最后，跟这个题目思路差不多，具体思路如下：

1. 创建两个指针 i 和 j，i 指向当前遍历到的元素，j 指向下一个非零元素
2. 从数组的第一个元素开始遍历
3. 当 i 指向的元素为0时，将j指向的元素复制到i指向的元素位置，i和j都后移一位。
4. 如果i指向的元素不是0，i和j都后移一位
5. 遍历完整个数组后，所有的0都会被移到数组的末尾

我们只需要遍历一遍数组原地操作即可。

---

✍🏻 代码实现：

class Solution:def moveZeroes(self, nums):i = 0j = 0while j < len(nums):if nums[j] != 0:nums[i] = nums[j]i += 1j += 1while i < len(nums):nums[i] = 0i += 1

---

🤔 这个题目也可以不使用双指针的方法，可以采用状态转移方程，代码会更简洁一点，具体思路如下：

1. 创建一个变量 zero，用来记录0的位置
2. 从数组的第一个元素开始遍历
3. 如果当前遍历到的元素不是0，就将它与zero位置的元素交换，并将zero位置后移一位
4. 遍历完整个数组后，所有的0都会被移到数组的末尾

---

✍🏻 代码实现：

class Solution:def moveZeroes(self, nums):zero = 0  # 记录“0”的位置for i in range(len(nums)):if nums[i] != 0:nums[i], nums[zero] = nums[zero], nums[i]zero += 1

---

• 题目三：[删除有序数组中的重复项](https://leetcode.cn/problems/remove-duplicates-from-sorted-array/)

📖 给你一个 升序排列 的数组 nums ，请你 原地 删除重复出现的元素，使每个元素 只出现一次 ，返回删除后数组的新长度。元素的 相对顺序 应该保持 一致 。

由于在某些语言中不能改变数组的长度，所以必须将结果放在数组nums的第一部分。更规范地说，如果在删除重复项之后有 k 个元素，那么 nums 的前 k 个元素应该保存最终结果。

将最终结果插入 nums 的前 k 个位置后返回 k 。

不要使用额外的空间，你必须在 原地 修改输入数组 并在使用 O(1) 额外空间的条件下完成。

示例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 。不需要考虑数组中超出新长度后面的元素。

提示：

1 <= nums.length <= 3 * 104
-104 <= nums[i] <= 104
nums 已按 升序 排列

---

🤔 题目的意思就是数组去重，但是我们不能使用集合的方法，所以需要转换思路，我们第一个题目做的就是移除元素，所以实现思路方面也是类似的，由于数组已经排好序，所以可以使用双指针来做，具体思路如下：

1. 创建两个指针 i 和 j，i 指向当前遍历到的元素，j 指向下一个元素
2. 从数组的第二个元素开始遍历
3. 当 j 指向的元素和 i 指向的元素不同时，就将 j 指向的元素赋值给 i+1的位置，i和j都后移一位
4. 如果j指向的元素和 i 指向的元素相同，j 后移一位
5. 遍历完整个数组后，所有重复项都会被删除。

这种思路只需要遍历一遍数组，并且是原地操作，不需要额外的空间。

---

✍🏻 代码实现：

class Solution:def removeDuplicates(self, nums):if not nums:return 0i = 0for j in range(1, len(nums)):if nums[j] != nums[i]:i += 1nums[i] = nums[j]return i + 1

---

• 题目四：[有序数组的平方](https://leetcode.cn/problems/squares-of-a-sorted-array/)

📖 给你一个按 **非递减顺序**排序的整数数组 `nums`，返回 **每个数字的平方** 组成的新数组，要求也按 **非递减顺序**排序。

示例1：

输入：nums = [-4,-1,0,3,10]
输出：[0,1,9,16,100]
解释：平方后，数组变为 [16,1,0,9,100]
排序后，数组变为 [0,1,9,16,100]

示例2：

输入：nums = [-7,-3,2,3,11]
输出：[4,9,9,49,121]

提示：

输入：nums = [-7,-3,2,3,11]
输出：[4,9,9,49,121]

---

🤔 这道题也是考察的我们对双指针法的理解和使用，我们使用双指针法，左指针指向最左边，右指针指向最右边。 我们每次比较两个指针指向的数的绝对值的大小，将较大的数的平方放入答案数组中。因为题目要求结果是非递减排序，所以每次将较小的数平方放入答案数组的最右边。具体的解题思路如下：

1. 创建一个结果数组result，并初始化为0。
2. 创建三个指针，i,j,k。 i 指向数组最左边,j指向数组最右边,k指向结果数组最右边
3. 使用while循环，当i小于等于j时循环，比较i指向的数和j指向的数的绝对值的大小。
4. 如果i指向的数的绝对值大于j指向的数的绝对值，就将i指向的数的平方放入result中，并将i指针后移一位。否则将j指向的数的平方放入result中，并将j指针前移一位。
5. 最后返回result

这种思路只需要遍历一遍数组，并且是原地操作，不需要额外的空间。

---

✍🏻 代码实现：

class Solution:def sortedSquares(self, nums):n = len(nums)result = [0] * ni, j = 0, n - 1k = n - 1while i <= j:if abs(nums[i]) > abs(nums[j]):result[k] = nums[i] ** 2i += 1else:result[k] = nums[j] ** 2j -= 1k -= 1return result

也可以这样去写：

class Solution:def sortedSquares(self, nums):reslut = [-1] * len(nums)k = len(nums) - 1i = 0j = len(nums) - 1while i <= j: if nums[i] ** 2 > nums[j] **2:reslut[k] = nums[i] ** 2i += 1else:reslut[k] = nums[j] ** 2j -= 1k -= 1return reslut

---

⚠️ 在使用双指针法解决数组问题时，需要注意以下几点：

1. 了解题目要求，判断是否适用双指针法。
2. 确定指针的初始位置和移动规则。
3. 注意每次移动指针时的边界条件。
4. 注意在循环中进行的比较和赋值操作。
5. 注意结果数组的初始化和最终返回结果。
6. 注意空间复杂度，尽量使用原地算法。
7. 多加思考，多加练习。

使用双指针法解决数组问题时需要多加思考和观察，通过不断练习来提高自己的编程能力。

---

🏆 力扣上面有许多使用双指针法解决的数组问题，以下是一些经典题目的序号:

• 第26题：删除排序数组中的重复项
• 第27题：移除元素
• 第75题：颜色分类
• 第88题：合并两个有序数组
• 第67题：两数之和 II - 输入有序数组
• 第9题：长度最小的子数组
• 第53题：会议室 II
• 第45题：反转字符串中的元音字母
• 第67题：字符串的排列
• 第81题：最短无序连续子数组
• 第77题：有序数组的平方

这些题目都是双指针的经典题目，可以帮助你更好的理解双指针的思想。