北大硕士LeetCode算法专题课-数组相关问题

我会带着你远行 2024-03-30 17:00 17阅读 0赞

算法专题：

[北大硕士LeetCode算法专题课---算法复杂度介绍\_骨灰级收藏家的博客-CSDN博客][LeetCode_---_-CSDN]

[北大硕士LeetCode算法专题课-基础算法之排序\_骨灰级收藏家的博客-CSDN博客][LeetCode_-_-CSDN]

[北大硕士LeetCode算法专题课-基础算法查找\_骨灰级收藏家的博客-CSDN博客][LeetCode_-_-CSDN 1]

**数组相关问****题**

双指针

![122a294f2ef64d0aa30c7b65b9b4510b.png][]说明:

1.必须在原数组上操作，不能拷贝额外的数组。

2.尽量减少操作次数

解题思路：从左向右遍历数组，当遇到非零元素时将其复制到新的数组中，遍历结束后，新的数组剩余元素用0补齐

![8a035fc674fe453bab3ca03a2b9a8519.png][]

def moveZeroes(nums) -> None:  temp = []
    for i in range(len(nums)):
    if nums[i] != 0:  temp.append(nums[i])
    for i in range(len(temp)):  nums[i] = temp[i]
    for i in range(len(temp), len(nums)):  nums[i] = 0
    print(nums)

解题思路：使用两个指针i , j ，从左向右遍历数组，j用来记录非零元素的位置,当i 遇到非零元素时，将i指向的值赋值给j 指向的元素。i遍历结束后，从j的位置开始用0补齐

![c5cbbfd53bf2491380d24936a8ef96a7.png][]

![412893bb98984b18a426f9c11ab27e72.png][]

![f088645389c14e9cbc24fa5ce8c8614c.png][]

![f3c2c02835b942a4880dc9a422f37003.png][]

def moveZeroes2(nums) -> None:  j = 0
    for i in range(len(nums)):
    if nums[i] != 0:  nums[j] = nums[i]  j += 1
    
    for i in range(j, len(nums)):  nums[i] = 0

def moveZeroes3(nums) -> None:  j = 0
    for i in range(len(nums)):
    if nums[i] != 0:
    nums[j], nums[i] = nums[i], nums[j]  j += 1

**移除元素(LeetCode27)**

给你一个数组 nums 和一个值 val，你需要 **原****地** 移除所有数值等于 val 的元素，并返回移除后数组的新长度。 不要使用额外的数组空间，你必须仅使用 O(1) 额外空间并 **原****地** **修改输入数组**。

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

![e1f264f5e7d8476d89b3ef13dc2c128d.png][]

**思路及算****法**

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

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

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

整个过程保持不变的性质是：区间 **\[*****0,left*****)** 中的元素都不等于 ***val***。当左右指针遍历完输入数组以后，***left*** 的值就 是输出数组的长度。

这样的算法在最坏情况下（输入数组中没有元素等于 ***val***），左右指针各遍历了数组一次。

![19ac6824df0a44d98050def5197e46c4.png][]

![962ea36086e144368dc5aabaa9646017.png][]

def removeElement(nums, val):  """
    :type nums: List[int]
    :type val: int
    :rtype: int  """
    i = -1
    for j in range(len(nums)):
    if nums[j] != val:  i = i + 1
    nums[i] = nums[j]
    return i + 1

**复杂度分析****：**时间复杂度：O(n)，其中n是数组nums的长度 空间复杂度：O(1) 。

**删除有序数组中的重复项** **(LeetCode26)**

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

由于在某些语言中不能改变数组的长度，所以必须将结果放在数组nums的第一部分。更规范地说，如果在删除重复项之后有

k 个元素，那么 nums 的前 k 个元素应该保存最终结果。将最终结果插入 nums 的前 k 个位置后返回 k 。 **不要使用额外的空间**，你必须在 **原****地** 修改输入数组 并在使用 O(1) 额外空间的条件下完成。

示例 1：

输入：nums = \[0,0,1,1,1,2,2,3,3,4\]

输出：5, nums = \[0,1,2,3,4\]

![719c9ddd607145d486e54a74151083d3.png][]

![cafb19d240d84d7385f9171151b8775d.png][]

def removeDuplicates(nums):  if not nums:
    return 0
    
    n = len(nums)  fast = slow = 1  while fast < n:
    if nums[fast] != nums[fast - 1]:  nums[slow] = nums[fast]
    slow += 1
    fast += 1
    
    return slow

**颜色分类(LeetCode75)** **中****等**

给定一个包含红色、白色和蓝色，一共 n 个元素的数组，原地对它们进行排序，使得相同颜色的元素相邻， 并按照红色、白色、蓝色顺序排列。此题中，我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。

![29844a50845549b5a47d281b713ce00c.png][]

**方法一：计数排序**

两次遍历， 第一次统计0,1,2 出现的次数， 第二次按顺序生成数组

**方法二：双指针**

用两个指针分别用来交换 0 和 2，指针P0来交换 0，P2来交换 2，初始值P0为 0， P2初始值为n-1

P2是从右向左移动的，故从左向右遍历整个数组时，当遍历的位置超过P2遍历即可停止

从左向右遍历整个数组，设当前遍历到的位置为 i，对应的元素为 nums\[i\]

如果找到了 0，将其与 nums\[P0\] 进行交换，并将 P0向后移动一个位置 如果找到了 2，将其与 nums\[ P2\] 进行交换，并将P2向前移动一个位置

![cf56afb231d341b8a947944bcbd57c5e.png][]

![e2a79d6e410c437f929c456baa8bb200.png][]

def sortColors(nums):  n = len(nums)
    p0, p2 = 0, n - 1
    i = 0
    while i <= p2:
    while i <= p2 and nums[i] == 2:
    nums[i], nums[p2] = nums[p2], nums[i]  p2 -= 1
    if nums[i] == 0:
    nums[i], nums[p0] = nums[p0], nums[i]  p0 += 1
    i += 1

**复杂度分析：**时间复杂度：O(n)，其中n是数组nums的长度 空间复杂度：O(1) 。

[LeetCode_---_-CSDN]: https://blog.csdn.net/JACK_SUJAVA/article/details/128611560?spm=1001.2014.3001.5501
[LeetCode_-_-CSDN]: https://blog.csdn.net/JACK_SUJAVA/article/details/128624508?spm=1001.2014.3001.5501
[LeetCode_-_-CSDN 1]: https://blog.csdn.net/JACK_SUJAVA/article/details/128625648?spm=1001.2014.3001.5501
[122a294f2ef64d0aa30c7b65b9b4510b.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/b2a5bfaf7697446c930581fd0d74195d.png
[8a035fc674fe453bab3ca03a2b9a8519.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/b774fba285744cf6918c2634fdcc96ed.png
[c5cbbfd53bf2491380d24936a8ef96a7.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/7c26a9c387bf487f9b7a37f32bc1d91f.png
[412893bb98984b18a426f9c11ab27e72.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/b179468e7df247f8b69915ed6de80af7.png
[f088645389c14e9cbc24fa5ce8c8614c.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/07bf276a099241489b34270697397baa.png
[f3c2c02835b942a4880dc9a422f37003.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/e71e1bb161354ea48c0749d318ffcec9.png
[e1f264f5e7d8476d89b3ef13dc2c128d.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/fa64266957ab4cd9ac6ab4187c46c6bb.png
[19ac6824df0a44d98050def5197e46c4.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/fd417367e1bf4aa19065e269a917b556.png
[962ea36086e144368dc5aabaa9646017.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/947812cc67124f08848641e6b66881ea.png
[719c9ddd607145d486e54a74151083d3.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/014f80ea58784adbba073c79578eb36e.png
[cafb19d240d84d7385f9171151b8775d.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/257e0bdd8184453eb0c938b89b943307.png
[29844a50845549b5a47d281b713ce00c.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/887758ea327f480e8abe15e30de1c5fe.png
[cf56afb231d341b8a947944bcbd57c5e.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/3a8e1b8dde7043f5ab84a46fdc64fdcc.png
[e2a79d6e410c437f929c456baa8bb200.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/073c6645c8634c9b89c4d64443fa03e7.png