代码随想录算法训练营Day1实战解析（Python版）——数组篇Part01

目录

数组理论基础

704. 二分查找

题目

思路

情况一[left,right]

情况二[left,right）

27. 移除元素

题目

思路

暴力解法

双指针法（快慢指针法）

977.有序数组的平方

题目

暴力解法

双指针法

---

碎碎念版，话很多。

 

数组理论基础

文章链接：代码随想录

704. 二分查找

题目链接：704. 二分查找 – 力扣（LeetCode）

文章讲解：代码随想录

视频讲解：手把手带你撕出正确的二分法 | 二分查找法 | 二分搜索法 | LeetCode：704. 二分查找_哔哩哔哩_bilibili

题目

给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target  ，写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1。

示例 1:

输入: nums = [-1,0,3,5,9,12], target = 9
输出: 4
解释: 9 出现在 nums 中并且下标为 4

示例 2:

输入: nums = [-1,0,3,5,9,12], target = 2
输出: -1
解释: 2 不存在 nums 中因此返回 -1

提示：

1. 你可以假设 nums 中的所有元素是不重复的。
2. n 将在 [1, 10000]之间。
3. nums 的每个元素都将在 [-9999, 9999]之间。

思路

题目前提是：数组元素有序且不重复

二分法查找场景：用于在一个单调或者局部单调有序数组中查找一个符合某些条件的值，时间复杂度为O(logN)二分法查找

大白话就是，数组有序，先找中间点，中间点不是，再找中间点左边，左边再找中间点，找的范围越来越少；左边全找完了再找右边，从中间切一半，再切一半，循环下去。

两种情况：[left,right]，[left,riight)

情况一[left,right]

区间为[left,right]

循环条件为while（left<=right）right可以被取到所以可以=

中间点middle=（left+right）/2，但因为C和Java中int值有范围left和right相加太大的话可能会溢出，所以换一种写法，虽然python不会溢出（因为python中的整数是动态的不会溢出），但为了安全也换种写法middle=left+((right-left)/2),假设你站在数轴的 left 位置，要去 right 位置的一半处。你会先计算总路程 right - left，然后走一半的路程，即 left + (right - left) / 2。

因为是闭区间，所以分割完后的两个区间为[left,middle-1]和[middle+1,right]

from typing import List
#力扣部分开始
class solution:
    def search(self, nums: List[int], target: int) -> int:
        left,right=0,len(nums)-1 #闭区间,索引从0开始，len从1开始数，右边界索引是len(nums)-1
        while left<=right:
            middle=left+(right-left)//2#//向下取整输出整数
            if nums[middle]==target:
                return middle
            elif nums[middle]>target:#中间点大于目标，去左边看
                right=middle-1
            else:
                left=middle+1
        return -1#如果没有找到目标值，返回-1
#力扣部分结束
if __name__ == "__main__":
    solution=solution()  # 创建 solution 类的实例
    nums=[-1,0,3,5,9,12]  # 定义一个数组 nums
    target=9  # 定义需要查找的目标值 target
    result=solution.search(nums,target)
    print(result)

情况二[left,right）

区间为[left,right）

循环条件为while（left<right）right取不到所以不能=

中间点middle=（left+right）/2或middle=left+((right-left)/2)

因为是开区间，所以分割完后的两个区间为[left,middle）和[middle+1,right）

from typing import List
#力扣部分开始
class solution:
    def search(self, nums: List[int], target: int) -> int:
        left,right=0,len(nums) #开区间,右边界是len(nums),len从1开始数
        while left<right:
            middle=left+(right-left)//2#//向下取整输出整数
            if nums[middle]==target:
                return middle
            elif nums[middle]>target:#中间点大于目标，去左边看
                right=middle#取开区间，所以右边界可以取middle，[left,middle)
            else:
                left=middle+1
        return -1#如果没有找到目标值，返回-1
#力扣部分结束
if __name__ == "__main__":
    solution=solution()  # 创建 solution 类的实例
    nums=[-1,0,3,5,9,12]  # 定义一个数组 nums
    target=9  # 定义需要查找的目标值 target
    result=solution.search(nums,target)
    print(result)

两种情况只在函数部分区别，主函数是一样的。

27. 移除元素

题目链接：27. 移除元素 – 力扣（LeetCode）

文章讲解：代码随想录

视频讲解：数组中移除元素并不容易！ | LeetCode：27. 移除元素_哔哩哔哩_bilibili

题目

给你一个数组 nums 和一个值 val，你需要 原地 移除所有数值等于 val 的元素。元素的顺序可能发生改变。然后返回 nums 中与 val 不同的元素的数量。

假设 nums 中不等于 val 的元素数量为 k，要通过此题，您需要执行以下操作：

更改 nums 数组，使 nums 的前 k 个元素包含不等于 val 的元素。nums 的其余元素和 nums 的大小并不重要。

返回 k。

用户评测：

评测机将使用以下代码测试您的解决方案：

int[] nums = [...]; // 输入数组
int val = ...; // 要移除的值
int[] expectedNums = [...]; // 长度正确的预期答案。
                            // 它以不等于 val 的值排序。

int k = removeElement(nums, val); // 调用你的实现

assert k == expectedNums.length;
sort(nums, 0, k); // 排序 nums 的前 k 个元素
for (int i = 0; i < actualLength; i++) {
    assert nums[i] == expectedNums[i];
}

如果所有的断言都通过，你的解决方案将会 通过。

示例 1：

输入：nums = [3,2,2,3], val = 3
输出：2, nums = [2,2,_,_]
解释：你的函数函数应该返回 k = 2, 并且 nums 中的前两个元素均为 2。
你在返回的 k 个元素之外留下了什么并不重要（因此它们并不计入评测）。

示例 2：

输入：nums = [0,1,2,2,3,0,4,2], val = 2
输出：5, nums = [0,1,4,0,3,_,_,_]
解释：你的函数应该返回 k = 5，并且 nums 中的前五个元素为 0,0,1,3,4。
注意这五个元素可以任意顺序返回。
你在返回的 k 个元素之外留下了什么并不重要（因此它们并不计入评测）。

提示：

0 <= nums.length <= 100

0 <= nums[i] <= 50

0 <= val <= 100

思路

数组的元素在内存地址中是连续的，不能单独删除数组中的某个元素，只能覆盖

暴力解法

遍历，发现目标就把后面的所有元素前移，两个循环，1个遍历整个数组，一个在遍历的时候每次把目标后面的所有数依次前移。时间复杂度O(n^2)

while a<size 遍历整个数组的元素，不能=，下标从0开始

a+1<=b<size，b++遍历目标后半部分

nums[b-1]=num[b]把后半部分前移

from typing import List
#力扣部分开始
class Solution:
    def removeElement(self, nums: List[int], val: int) -> int:
        a=0
        size=len(nums)
        while a<size:
            if nums[a]==val:#找到目标元素
                for b in range(a+1,size):#所有后面的元素前移
                    nums[b-1]=nums[b]
                size-=1#索引长度更新
                a-=1#while循环中a会自增，所以这里需要减1，此时a指向的是移过来的新元素，while循环+1后会重新检查这个元素
            a+=1
        return size

#力扣部分结束
if __name__ == "__main__": 
    solution = Solution()  # 创建 Solution 类的实例
    nums = [3, 2, 2, 3]  # 定义一个数组 nums
    val = 3  # 定义需要移除的值 val
    result = solution.removeElement(nums, val)  # 调用 removeElement 方法，返回新数组的长度
    print("Updated array:", nums[:result])  # 打印更新后的数组（只显示有效部分）
    print("New length:", result)  # 打印新数组的长度

双指针法（快慢指针法）

通过一个快指针和慢指针在一个循环下完成两个循环的工作

快的一直往前走，指到目标后把后面的前移，慢的指到目标元素停下等后面的数前移，所以新数组长度按慢的

from typing import List  # 导入 List 类型

# 双向指针法
# 时间复杂度 O(n)
# 空间复杂度 O(1)
# 力扣部分开始
class Solution:
    def removeElement(self, nums: List[int], val: int) -> int:  # 使用 List[int] 作为类型注解
        slow,fast =0,0
        size=len(nums)
        while fast<size:#fast遍历数组
            if fast!=val:#fast一直后移，遇到非目标就给slow，遇到目标就不触发if条件，直接后移
                # 将非目标元素放到slow指针位置
                nums[slow]=nums[fast]
                slow+=1
            fast+=1
        return slow
# 力扣部分结束

if __name__ == "__main__": 
    solution = Solution()  # 创建 Solution 类的实例
    nums = [3, 2, 2, 3]  # 定义一个数组 nums
    val = 3  # 定义需要移除的值 val
    result = solution.removeElement(nums, val)  # 调用 removeElement 方法，返回新数组的长度
    print("Updated array:", nums[:result])  # 打印更新后的数组（只显示有效部分）
    print("New length:", result)  # 打印新数组的长度

977.有序数组的平方

题目链接：977. 有序数组的平方 – 力扣（LeetCode）

文章讲解：代码随想录

视频讲解： 双指针法经典题目 | LeetCode：977.有序数组的平方_哔哩哔哩_bilibili

题目

给你一个按 非递减顺序 排序的整数数组 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]

提示：

1 <= nums.length <= 104

-104 <= nums[i] <= 104

nums 已按 非递减顺序 排序

进阶：

请你设计时间复杂度为 O(n) 的算法解决本问题

暴力解法

class Solution:
    def sortedSquares(self, nums: List[int]) -> List[int]:
        a=0
        size=len(nums)
        while a<size:
            nums[a]=nums[a]*nums[a]
            a+=1
        nums.sort()#快速排序
        return nums

这个时间复杂度是 O(n + nlogn)，一个循环n+快速排序 O(n + nlogn)

双指针法

数组其实是有序的， 只不过负数平方之后可能成为最大数了

那么数组平方的最大值就在数组的两端，不是最左边就是最右边，不可能是中间，因为给的数组就是有序的

left和right分别指向最左和最右，向中间移动，两个平方对比，谁大谁放进新数组最后面

if nums[left]*nums[left]>=nums[right]*nums[right]则result[a–]=nums[left]*nums[left]

from typing import List
# 力扣部分开始
class Solution:
    def sortedSquares(self, nums: List[int]) -> List[int]:
        left,right=0,len(nums)-1
        result=[0]*len(nums)# 初始化结果数组，长度与输入数组相同
        for a in range(len(nums)-1,-1,-1):  # 从后向前遍历,不用考虑left和right的顺序，因为结果数组的长度是固定的
            # 比较左右两边的绝对值，取较大的平方值放入结果数组
            # 这里的a是结果数组的索引，从最后一个元素开始填充
            if abs(nums[left])>abs(nums[right]):
                result[a]=nums[left]**2
                left+=1
            else:
                result[a]=nums[right]**2
                right-=1
        return result  # 返回结果数组

# 力扣部分结束
if __name__ == "__main__":  # 主函数入口，确保代码只在直接运行时执行
    solution = Solution()  # 创建 Solution 类的实例
    nums = [-4,-1,0,3,10]  # 定义一个数组 nums
    result = solution.sortedSquares(nums) 
    print(result)  # 打印更新后的数组

作者：清水泛轻舟