leetcode 题库 88答案
时间: 2024-01-11 11:00:34 浏览: 38
leetcode题库中的第88题是"合并两个有序数组"。该问题要求将两个有序数组合并为一个有序数组。
解答如下:
首先,我们可以创建一个新数组来存储合并的结果。同时,我们可以使用双指针的方式来进行遍历和比较。
我们分别定义两个指针,分别指向两个数组的末尾,然后从后往前遍历数组元素。
比较两个指针指向的元素大小,将较大的元素放入新数组的末尾,并将该元素的指针往前移动一位。
当其中一个数组的指针移动到了开头时,我们就可以将另一个数组剩余的元素全部放入新数组中。
最后得到的新数组就是两个有序数组合并之后的结果。
以下是具体的代码实现:
```python
def merge(nums1, m, nums2, n):
# 定义指针p1和p2分别指向两个数组的末尾
p1, p2 = m - 1, n - 1
# 定义指针p指向新数组的末尾
p = m + n - 1
while p1 >= 0 and p2 >= 0:
if nums1[p1] > nums2[p2]:
nums1[p] = nums1[p1]
p1 -= 1
else:
nums1[p] = nums2[p2]
p2 -= 1
p -= 1
# 将nums2中剩余的元素放入nums1中
while p2 >= 0:
nums1[p] = nums2[p2]
p2 -= 1
p -= 1
# 测试
nums1 = [1, 2, 3, 0, 0, 0]
m = 3
nums2 = [2, 5, 6]
n = 3
merge(nums1, m, nums2, n)
print(nums1) # [1, 2, 2, 3, 5, 6]
```
以上就是合并两个有序数组的解答,时间复杂度为O(m+n),其中m和n分别为两个数组的长度。