当前位置： 面试刷题>> 合并两个有序数组(经典算法150题)
### 题目描述
合并两个有序数组是一个常见的算法问题，具体描述如下：
给定两个已排序的整数数组 `nums1` 和 `m`，`nums2` 和 `n`，其中 `m` 是 `nums1` 的长度，`n` 是 `nums2` 的长度。你需要将 `nums2` 合并到 `nums1` 中，**使得 `nums1` 的前 `m + n` 个元素包含合并后的有序数组**。注意，`nums1` 的初始长度为 `m`，且 `nums1` 有足够的空间来存储合并后的数组，即 `nums1` 的大小至少为 `m + n`。你可以假设 `nums1` 和 `nums2` 是按非递减顺序排列的。
**注意**： 请不要使用额外的数组空间来合并这两个数组，你只能在 `nums1` 上就地修改，并且不能改变 `nums1` 和 `nums2` 的原始长度（即 `nums1` 的原始长度为 `m`，`nums2` 的原始长度为 `n`）。
### 示例
假设 `nums1 = [1,2,3,0,0,0]`，`m = 3`，`nums2 = [2,5,6]`，`n = 3`，则合并后的 `nums1` 应该为 `[1,2,2,3,5,6]`。
### PHP 代码示例
```php
function merge($nums1, &$m, $nums2, $n) {
$p1 = $m - 1; // nums1 的有效末尾索引
$p2 = $n - 1; // nums2 的末尾索引
$p = $m + $n - 1; // 合并后数组的末尾索引
while ($p1 >= 0 && $p2 >= 0) {
if ($nums1[$p1] > $nums2[$p2]) {
$nums1[$p] = $nums1[$p1];
$p1--;
} else {
$nums1[$p] = $nums2[$p2];
$p2--;
}
$p--;
}
// 如果 nums2 还有剩余元素，将它们复制到 nums1
while ($p2 >= 0) {
$nums1[$p] = $nums2[$p2];
$p2--;
$p--;
}
// 更新 m 的值，因为 nums1 的长度现在为 m + n
$m += $n;
}
// 示例用法
$nums1 = [1, 2, 3, 0, 0, 0];
$m = 3;
$nums2 = [2, 5, 6];
$n = 3;
merge($nums1, $m, $nums2, $n);
print_r($nums1); // 输出 [1, 2, 2, 3, 5, 6]
```
### Python 代码示例
```python
def merge(nums1, m, nums2, n):
p1, p2 = m - 1, n - 1
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]
```
这些示例展示了如何在 PHP 和 Python 中实现合并两个有序数组的问题，遵循了题目要求，并且没有使用额外的数组空间。