代码随想录算法训练营 Day 1
Published:
数组基础
- 索引从0开始
- 常用函数：append，pop， extend
Q1. LeetCode 704
解法1：左闭右开区间
class Solution:
def search(self, nums: List[int], target: int) -> int:
left, right = 0, len(nums)
while left < right:
mid = left + (right - left) // 2
if nums[mid] == target:
return mid
elif nums[mid] < target:
left = mid + 1
else:
right = mid
return -1
解法2: 左闭右闭区间
class Solution:
def search(self, nums: List[int], target: int) -> int:
left, right = 0, len(nums) - 1
while left <= right:
mid = left + (right - left) // 2
if nums[mid] == target:
return mid
elif nums[mid] < target:
left = mid + 1
else:
right = mid - 1
return -1
复杂度分析
时间复杂度：O($logn$) 空间复杂度：O(1)
两种解法的区别
- 右端点的初始值：[left, right)中右端点不会被考虑，因此设定为数组的长度才能包含整个数组
- 区间左右端点是否可以相等(循环条件)：[left, right)端点不能相等 (e.g., [2,2)数学不成立)；而[left, right]则可以相等 (e.g., [2,2]包含一个值)
- 右端点的更新是否需要减1: [left, right]需要更新为mid - 1，因为中间值已经能够确定不是目标值
Q2. LeetCode 27
解法1: 暴力法
class Solution:
def removeElement(self, nums: List[int], val: int) -> int:
i = 0
n = len(nums)
while i < n:
if nums[i] == val:
for j in range(i + 1, n):
nums[j - 1] = nums[j]
n -= 1
i -= 1 # 现在索引i的值变成了新的值，需要再一次判断是否等于val
i += 1
return n
复杂度分析
时间复杂度：O($n^2$) 空间复杂度：O(1)
解法2: 快慢指针法
思路：快指针正常移动的过程中，遇到val值不同的数字，将其赋给慢指针
class Solution:
def removeElement(self, nums: List[int], val: int) -> int:
slow = 0
n = len(nums)
for fast in range(n):
if nums[fast] != val:
nums[slow] = nums[fast]
slow += 1
return slow
class Solution:
def removeElement(self, nums: List[int], val: int) -> int:
n = len(nums)
left, right = 0, n - 1
while left <= right:
# 可能出现连续多个符合条件的数字，因此使用while循环
# 左指针找到首次出现等于val的数字
while left <= right and nums[left] != val:
left += 1
# 右指针找到首次不等于val的数字, 后面与左指针进行交换
while left <= right and nums[right] == val:
right -= 1
if left < right:
nums[left] = nums[right]
left += 1
right -= 1
return left
复杂度分析
时间复杂度：O($n$) 空间复杂度：O(1)
双指针法
- 适用于降低复杂度，在一次循环中完成两次循环的工作
- 如何移动指针： 快慢指针法中，主要考虑移动慢指针，覆盖等于val的数字；对撞指针中，双向指针都需要考虑，但条件不同
Q3. LeetCode 977
解法1: 暴力法
class Solution:
def sortedSquares(self, nums: List[int]) -> List[int]:
res = []
for num in nums:
res.append(num ** 2)
res.sort()
return res
复杂度分析
时间复杂度：O($nlogn$) 空间复杂度：O($n$)
Note: sort()函数的复杂度为O($nlogn$)
解法2: 双指针法
思路：原数组是有序的，因此最大的平方值只可能出现在数组的两端，因此可以用双指针法解决
class Solution:
def sortedSquares(self, nums: List[int]) -> List[int]:
i, j = 0, len(nums) - 1
res = []
while i <= j:
r1 = nums[i] ** 2
r2 = nums[j] ** 2
if r1 < r2:
res.append(r2)
j -= 1
else:
res.append(r1)
i += 1
return res[::-1]
复杂度分析
时间复杂度：O($n$) 空间复杂度：O($n$)