轮转数组
给定一个整数数组 nums，将数组中的元素向右轮转 k 个位置，其中 k 是非负数。
示例 1:
输入: nums = [1,2,3,4,5,6,7], k = 3 输出:[5,6,7,1,2,3,4]解释: 向右轮转 1 步:[7,1,2,3,4,5,6]向右轮转 2 步:[6,7,1,2,3,4,5]向右轮转 3 步:[5,6,7,1,2,3,4]
示例 2:
输入：nums = [-1,-100,3,99], k = 2
输出：[3,99,-1,-100]
解释:
向右轮转 1 步: [99,-1,-100,3]
向右轮转 2 步: [3,99,-1,-100]
首次尝试
- 通过计算
move = k % len(nums)获取实际需要轮转的步数。 - 将前部分
nums[:len(nums)-move]提取出来作为target。 - 删除前部分元素，并将其追加到数组末尾，完成轮转。
代码
class Solution:
def rotate(self, nums: List[int], k: int) -> None:
"""
Do not return anything, modify nums in-place instead.
"""
move = k % len(nums)
target = nums[:len(nums)-move]
del nums[:len(nums)-move]
nums.extend(target)时间复杂度：
- 切片操作
nums[:len(nums)-move]和删除操作del nums[:len(nums)-move]的复杂度均为 $O(n)$。 - 扩展操作
nums.extend(target)的复杂度也是 $O(n)$。 - 总复杂度为 $O(n)$
空间复杂度：
- 使用了一个额外的列表
target，空间复杂度为 $O(n)$。但题目要求“修改数组，尽量减少空间使用”，这个实现未完全满足要求。
改进方法
想法
代码
class Solution:
def rotate(self, nums: List[int], k: int) -> None:
"""
Do not return anything, modify nums in-place instead.
"""
def reverse(i: int, j: int) -> None:
while i < j:
nums[i], nums[j] = nums[j], nums[i]
i += 1
j -= 1
n = len(nums)
k %= n # 轮转 k 次等于轮转 k%n 次
reverse(0, n - 1)
reverse(0, k - 1)
reverse(k, n - 1)复杂度
- 时间复杂度：O(n)，其中 n 是 nums 的长度。
- 空间复杂度：O(1)
除自身以外数组的乘积
给你一个整数数组 nums，返回 数组 answer ，其中 answer[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积 。
题目数据 保证 数组 nums之中任意元素的全部前缀元素和后缀的乘积都在 32 位 整数范围内。
请 不要使用除法，且在 O(n) 时间复杂度内完成此题。
示例 1:
输入: nums = [1,2,3,4]
输出: [24,12,8,6]
示例 2:
输入: nums = [-1,1,0,-3,3]
输出: [0,0,9,0,0]
尝试
思路
前缀乘积和后缀乘积：
- 使用两个列表
pre和last分别存储从左到右的前缀乘积和从右到左的后缀乘积。 - 然后根据这两个列表来计算结果数组
result，使得每个位置的值等于其左侧前缀乘积和右侧后缀乘积的乘积。
实现流程：
- 初始化前缀乘积列表
pre和后缀乘积列表last，并分别在循环中更新它们。 - 通过组合前缀乘积和后缀乘积得到了结果数组。
代码
class Solution:
def productExceptSelf(self, nums: List[int]) -> List[int]:
pre = [nums[0]]
last = [nums[-1]]
result = []
for i in range(1,len(nums)):
pre.append(nums[i]*pre[i-1])
last.append(nums[-i-1]*last[i-1])
result.append(last[-2])
for i in range(1, len(nums)-1):
result.append(pre[i-1]*last[len(nums)-i-2])
result.append(pre[-2])
return result优化
空间复杂度优化：
- 可以通过在一个遍历中同时更新结果数组和一个变量来避免使用额外空间存储前缀和后缀。
逻辑简化：
- 合理初始化前缀和后缀乘积，减少单独的边界情况处理。
- 使用简化的计算逻辑和变量。
特殊情况处理：
- 增加对
nums为空或者只有一个元素时的处理，确保代码健壮性。
代码
class Solution:
def productExceptSelf(self, nums: List[int]) -> List[int]:
n = len(nums)
result = [1] * n # 初始化结果数组为全 1
# Step 1: 从左到右计算前缀乘积
left_product = 1
for i in range(n):
result[i] = left_product
left_product *= nums[i] # 更新左侧乘积
# Step 2: 从右到左计算后缀乘积，并更新结果数组
right_product = 1
for i in range(n - 1, -1, -1):
result[i] *= right_product
right_product *= nums[i] # 更新右侧乘积
return result复杂度
时间复杂度：O(n)
- 两次遍历数组，分别计算前缀乘积和后缀乘积。
空间复杂度：O(1)
- 使用常量额外变量
left_product和right_product。
总结
- 移除多余的数组：通过变量代替
pre和last数组，节省空间。 - 避免重复计算：在单次遍历中直接更新结果数组，逻辑更加紧凑。
- 边界处理一致性：消除对
result边界值的单独处理，使代码更清晰。
缺失的第一个正数
给你一个未排序的整数数组 nums ，请你找出其中没有出现的最小的正整数。
请你实现时间复杂度为 O(n) 并且只使用常数级别额外空间的解决方案。
示例 1：
输入：nums = [1,2,0]
输出：3
解释：范围 [1,2] 中的数字都在数组中。
示例 2：
输入：nums = [3,4,-1,1]
输出：2
解释：1 在数组中，但 2 没有。
示例 3：
输入：nums = [7,8,9,11,12]
输出：1
解释：最小的正数 1 没有出现。
首次提交
- 不使用排序，避免O(n \log n) 的时间开销。
- 通过数组索引与值的关系进行调整，达到空间 O(1)的优化。
错误代码
class Solution:
def firstMissingPositive(self, nums: List[int]) -> int:
n = len(nums)
for i in range(n):
if 0 < nums[i] < n:
nums[nums[i]-1] = nums[i]
for i in range(n):
if nums[i] != i+1:
return i+1
else:
return n+1代码问题分析
- 缺陷 1：未正确交换元素：
- 代码中只直接赋值
nums[nums[i]-1] = nums[i]，没有考虑到两者需要互换。 - 如果目标位置已经存在一个值（可能是重复值或其他正确的值），直接赋值会覆盖目标值，导致数据丢失。
- 代码中只直接赋值
- 缺陷 2：条件范围不完整：
- 判断条件
0 < nums[i] < n有误，应该是1 <= nums[i] <= n。 - 未正确处理超出范围或重复的值（如负数、零、大于 n 的数）。
- 判断条件
- 边界情况：
- 对于边界输入（如空数组、所有元素都大于 n 等），代码未能正确处理。
改进
代码
class Solution:
def firstMissingPositive(self, nums: List[int]) -> int:
n = len(nums)
# Step 1: 交换元素，将每个正整数尽量放到对应的位置
for i in range(n):
while 1 <= nums[i] <= n and nums[nums[i] - 1] != nums[i]:
# 交换 nums[i] 和 nums[nums[i] - 1]
nums[nums[i] - 1], nums[i] = nums[i], nums[nums[i] - 1]
# Step 2: 找到第一个位置不匹配的索引
for i in range(n):
if nums[i] != i + 1:
return i + 1
# 如果所有正整数都在正确位置，返回 n + 1
return n + 1总结
while 1 <= nums[i] <= n and nums[nums[i] - 1] != nums[i]: 的含义
1 <= nums[i] <= n：- 作用：确保我们只处理 有效范围内的正整数。
- 数组可能包含：
- 非正整数（如 0 或负数）；
- 大于 n 的整数。
- 这些数字无法被放置在有效范围 1≤x≤n 的索引位置（因为索引超出范围），所以直接跳过。
nums[nums[i] - 1] != nums[i]：- 作用：确保当前数字还没有被放到正确的位置上。
- 假设当前数字为
x = nums[i]，它应该被放在索引上。如果：nums[x-1] == x，说明x已经在正确位置上，无需交换；- 否则，我们需要将
x和其目标位置上的数字交换。
while 循环的作用
while 循环确保当前元素被反复检查并交换，直到它被放到正确的位置或者不符合条件为止。
- 每次交换后，
nums[i]可能变成一个新数字，因此需要重新检查是否需要进一步交换。 - 通过这个循环，一个数字最多只会被移动一次到正确的位置上。