88.合并两个有序数组
88.1 题目
给你两个按非递减顺序排列的整数数组 nums1 和 nums2，另有两个整数 m 和 n，分别表示 nums1 和 nums2 中的元素数目。
请你合并 nums2 到 nums1 中，使合并后的数组同样按非递减顺序排列。
注意：最终，合并后数组不应由函数返回，而是存储在数组 nums1 中。为了应对这种情况，nums1 的初始长度为 m + n，其中前 m 个元素表示应合并的元素，后 n 个元素为 0，应忽略。nums2 的长度为 n。
示例 1：
输入：nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3
输出：[1,2,2,3,5,6]
解释：需要合并 [1,2,3] 和 [2,5,6]。
合并结果是 [1,2,2,3,5,6]，其中 斜体加粗 标注的为 nums1 中的元素。
示例 2：
输入：nums1 = [1], m = 1, nums2 = [], n = 0
输出：[1]
解释：需要合并 [1] 和 []。
合并结果是 [1]。
示例 3：
输入：nums1 = [0], m = 0, nums2 = [1], n = 1
输出：[1]
解释：需要合并的数组是 [] 和 [1]。
合并结果是 [1]。
注意，因为 m = 0，所以 nums1 中没有元素。nums1 中仅存的 0 仅仅是为了确保合并结果可以顺利存放到 nums1 中。
88.2 题解
双指针从后往前遍历
// 方法一：双指针从后往前遍历
// 从 nums1 和 nums2 的尾部开始，比较两者元素大小，将较大的元素放到 nums1 的尾部。
static void Merge1(int[] nums1, int m, int[] nums2, int n)
{
// 如果 nums2 的长度为 0，则直接返回，无需合并
if (n == 0) return;
// 初始化 nums1、nums2 和合并后数组的索引
int nums1Index = m - 1; // nums1 数组的末尾索引
int nums2Index = n - 1; // nums2 数组的末尾索引
int nowSetIndex = nums1.Length - 1; // 合并后数组的末尾索引
// 循环直到其中一个数组的所有元素都被合并完
while (nums1Index >= 0 && nums2Index >= 0)
{
// 如果 nums2 中的当前元素大于或等于 nums1 中的当前元素
if (nums2[nums2Index] >= nums1[nums1Index])
{
// 将 nums2 中的当前元素放入合并后数组中，并移动 nums2Index 指针
nums1[nowSetIndex] = nums2[nums2Index];
nums2Index--;
}
else
{
// 如果 nums2 中的当前元素小于 nums1 中的当前元素
// 将 nums1 中的当前元素移动到合并后数组的相应位置，并移动 nums1Index 指针
(nums1[nowSetIndex], nums1[nums1Index]) = (nums1[nums1Index], nums1[nowSetIndex]);
nums1Index--;
}
// 移动合并后数组的索引指针
nowSetIndex--;
}
// 如果 nums2 中还有剩余元素，将其逐个放入合并后数组中
while (nums2Index >= 0)
{
nums1[nowSetIndex] = nums2[nums2Index];
nowSetIndex--;
nums2Index--;
}
}
Array.Copy 和排序
// 方法二：Array.Copy 和排序
// 将 nums2 复制到 nums1 的末尾，然后对整个数组进行排序。
static void Merge2(int[] nums1, int m, int[] nums2, int n)
{
Array.Copy(nums2, 0, nums1, m, n);
Array.Sort(nums1);
}
合并后排序
// 方法三：合并后排序
// 将 nums1 和 nums2 合并到一个新数组，然后对新数组进行排序，并将结果复制回 nums1。
static void Merge3(int[] nums1, int m, int[] nums2, int n)
{
int[] mergedArray = new int[m + n];
Array.Copy(nums1, 0, mergedArray, 0, m);
Array.Copy(nums2, 0, mergedArray, m, n);
Array.Sort(mergedArray);
Array.Copy(mergedArray, nums1, m + n);
}
88.3 代码
using System;
public class ListNode
{
public int val;
public ListNode next;
public ListNode(int val = 0, ListNode next = null)
{
this.val = val;
this.next = next;
}
}
class Program
{
static void Main()
{
#region 题目
// 给你两个按 非递减顺序 排列的整数数组 nums1 和 nums2，另有两个整数 m 和 n ，分别表示 nums1 和 nums2 中的元素数目。
// 请你 合并 nums2 到 nums1 中，使合并后的数组同样按 非递减顺序 排列。
// 注意：最终，合并后数组不应由函数返回，而是存储在数组 nums1 中。为了应对这种情况，nums1 的初始长度为 m + n，其中前 m 个元素表示应合并的元素，后 n 个元素为 0 ，应忽略。nums2 的长度为 n 。
// 示例 1：
// 输入：nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3
// 输出：[1,2,2,3,5,6]
// 解释：需要合并 [1,2,3] 和 [2,5,6] 。
// 合并结果是 [1,2,2,3,5,6] ，其中斜体加粗标注的为 nums1 中的元素。
// 示例 2：
// 输入：nums1 = [1], m = 1, nums2 = [], n = 0
// 输出：[1]
// 解释：需要合并 [1] 和 [] 。
// 合并结果是 [1] 。
// 示例 3：
// 输入：nums1 = [0], m = 0, nums2 = [1], n = 1
// 输出：[1]
// 解释：需要合并的数组是 [] 和 [1] 。
// 合并结果是 [1] 。
// 注意，因为 m = 0 ，所以 nums1 中没有元素。nums1 中仅存的 0 仅仅是为了确保合并结果可以顺利存放到 nums1 中。
#endregion
#region 测试
// 示例 1
int[] nums1_1 = { 1, 2, 3, 0, 0, 0 };
int m1 = 3;
int[] nums2_1 = { 2, 5, 6 };
int n1 = 3;
Merge1(nums1_1, m1, nums2_1, n1);
PrintArray("示例1", "方法1", nums1_1);
// 示例 2
int[] nums1_2 = { 1 };
int m2 = 1;
int[] nums2_2 = { };
int n2 = 0;
Merge2(nums1_2, m2, nums2_2, n2);
PrintArray("示例2", "方法2", nums1_2);
// 示例 3
int[] nums1_3 = { 0 };
int m3 = 0;
int[] nums2_3 = { 1 };
int n3 = 1;
Merge1(nums1_3, m3, nums2_3, n3);
PrintArray("示例3", "方法3", nums1_3);
#endregion
}
#region 答案
// 方法一：双指针从后往前遍历
// 从 nums1 和 nums2 的尾部开始，比较两者元素大小，将较大的元素放到 nums1 的尾部。
static void Merge1(int[] nums1, int m, int[] nums2, int n)
{
// 如果 nums2 的长度为 0，则直接返回，无需合并
if (n == 0) return;
// 初始化 nums1、nums2 和合并后数组的索引
int nums1Index = m - 1; // nums1 数组的末尾索引
int nums2Index = n - 1; // nums2 数组的末尾索引
int nowSetIndex = nums1.Length - 1; // 合并后数组的末尾索引
// 循环直到其中一个数组的所有元素都被合并完
while (nums1Index >= 0 && nums2Index >= 0)
{
// 如果 nums2 中的当前元素大于或等于 nums1 中的当前元素
if (nums2[nums2Index] >= nums1[nums1Index])
{
// 将 nums2 中的当前元素放入合并后数组中，并移动 nums2Index 指针
nums1[nowSetIndex] = nums2[nums2Index];
nums2Index--;
}
else
{
// 如果 nums2 中的当前元素小于 nums1 中的当前元素
// 将 nums1 中的当前元素移动到合并后数组的相应位置，并移动 nums1Index 指针
(nums1[nowSetIndex], nums1[nums1Index]) = (nums1[nums1Index], nums1[nowSetIndex]);
nums1Index--;
}
// 移动合并后数组的索引指针
nowSetIndex--;
}
// 如果 nums2 中还有剩余元素，将其逐个放入合并后数组中
while (nums2Index >= 0)
{
nums1[nowSetIndex] = nums2[nums2Index];
nowSetIndex--;
nums2Index--;
}
}
// 方法二：Array.Copy 和排序
// 将 nums2 复制到 nums1 的末尾，然后对整个数组进行排序。
static void Merge2(int[] nums1, int m, int[] nums2, int n)
{
Array.Copy(nums2, 0, nums1, m, n);
Array.Sort(nums1);
}
// 方法三：合并后排序
// 将 nums1 和 nums2 合并到一个新数组，然后对新数组进行排序，并将结果复制回 nums1。
static void Merge3(int[] nums1, int m, int[] nums2, int n)
{
int[] mergedArray = new int[m + n];
Array.Copy(nums1, 0, mergedArray, 0, m);
Array.Copy(nums2, 0, mergedArray, m, n);
Array.Sort(mergedArray);
Array.Copy(mergedArray, nums1, m + n);
}
#endregion
#region 辅助方法
static void PrintArray(string example, string method, int[] array)
{
Console.Write($"{example} {method} 输出：[");
for (int i = 0; i < array.Length; i++)
{
Console.Write(array[i]);
if (i < array.Length - 1)
Console.Write(", ");
}
Console.Write("]\n\n");
}
#endregion
}
88.4 运行结果
示例1 方法1 输出：[1, 2, 2, 3, 5, 6]
示例2 方法2 输出：[1]
示例3 方法3 输出：[1]
转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论，也可以邮件至 785293209@qq.com
