两个非递减顺序表合并成一个非递减顺序表

两个非递减顺序表合并成一个非递减顺序表

• 引入

以下这个例题的描述是关于合并两个有序的数组，然后合并之后同样也是一个非递减的顺序排列

但是我名这里讲的不是顺序表，而是封装成一个顺序表，但是我们这里的顺序表其实底层同样是一个数组，所以解题的思路完全相同，我们接下来要讲的就是“两个非递减顺序表合成的一个非递减的顺序表”。

合并两个有序数组

给你两个按非递减顺序排列的整数数组 nums 1 和 nums 2，另有两个整数 m 和 n ，分别表示 nums 1 和 nums 2 中的元素数目。

---

请你合并 nums 2 到 nums 1 中，使合并后的数组同样按非递减顺序排列。

---

注意：最终，合并后数组不应由函数返回，而是存储在数组 nums 1 中。为了应对这种情况，nums 1 的初始长度为 m + n，其中前 m 个元素表示应合并的元素，后 n 个元素为 0 ，应忽略。Nums 2 的长度为 n 。

• 我们是合并两个顺序表，只是多了一个封装顺序表的步骤，但是该题目的解法思路是大同小异的。

❤️理清思路

• 非递减顺序表

  非递减就是 “增”，而顺序表就是线性表的一种，其逻辑结构是顺序结构，同时其物理结构也和逻辑结构相同的结构，在计算机中存储的物理结构也是连续存储的。

• 题目要求

  将两个 “非递减顺序表” 合成一个非递减的顺序表，那么我们在实现这个方法的时候需要传两个 “非递减顺序表”作为参数，然后我们就在方法中对这两个顺序表进行操作。并且最后合成的顺序表同样非递减的顺序表，那么我们在实现方法的时候就必须保证顺序表的顺序一致

• 思路

  自定义一个"顺序表"数据结构，然后定义一个方法 merge ()，这个方法要求是传进去两个“非递减的顺序表对象” 参数，分别是 list 1 和 list 2；然后我们在方法中重新 new 一个“新的非递减的顺序表对象”newList，然后定义三个指针分别指向这三个顺序表下标为 0 的位置，利用“穿针引线法”，完成合并工作。

• 穿针引线法

  我在这里将这种方式描述为 "穿针引线法"是因为真的很形象，但是其实如果是在链表中这样称呼，似乎更加合适。

  我们分别让 i 和 j 永远指向即将进行比较大小的数据元素，然后让 k 在新顺序表中永远都指向“索引等于顺序表有效长度“ 的地方，然后等待 i 和 j 比较的结果的数据元素的插入，直到任意一个顺序表遍历完，
  如果同时遍历完, 那么合并的工作做完了；如果其中一个顺序表遍历玩，而另外一个没有遍历完，那么就把更长的顺序表直接加到 newList 顺序表中。
  综上所述，就完成了两个非递减顺序表的合并工作。