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

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

引入

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

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

合并两个有序数组

给你两个按非递减顺序排列的整数数组 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 顺序表中。
综上所述，就完成了两个非递减顺序表的合并工作。

🚀代码实现

package TextReport;  import java.util.Arrays;  public class MyArrayList {  //    存放数据的数组  public int[] elem;  //    记录数组的有效长度  public int usedSize;  //    常量，用来给数组初始化容量  public static final int DEFAULT_CAPACITY = 5;  //    构造方法  public MyArrayList() {  this.elem = new int[DEFAULT_CAPACITY];  }  public MyArrayList(int defaultSize) {  this.elem = new int[defaultSize];  }  //    打印顺序表的方法（顺序表中有几个有效元素就打印几个有效元素）  public void display() {  for (int i = 0; i < usedSize; i++) {  System.out.print(this.elem[i] + " ");  }  System.out.println();  }  //    输入（新增加元素，默认在顺序表的最后一个元素的下一个位置上新增）  public void add(int data) {  try {  if (isFull()) {  elem = Arrays.copyOf(elem, 2 * elem.length);  }  } catch (NegativeArraySizeException e) {  e.printStackTrace();  }  Elem[usedSize++] = data;  }  //    在指定位置索引为 pos 新增元素  Public void addPos (int data, int pos) {  //先判断下标是否合法  Try {  CheckedAddPos (pos);  If (isFull ()) {  Elem = Arrays.CopyOf (elem, 2 * elem. Length);  }  For (int i = usedSize - 1; i > pos; i--) {  Elem[i + 1] = elem[i];  }  Elem[pos] = data;  UsedSize++;  } catch (PosIndexIllegalException e) {  e.getMessage ();  }  }  //判断顺序表中是否包含某个元素  Public boolean contains (int data) {  For (int i = 0; i < usedSize; i++) {  If (data == elem[i]) {  Return true;  }  }  Return false;  }  //返回某个元素的在容器中的索引  Public int indexOf (int find) {  For (int i = 0; i < usedSize; i++) {  If (find == elem[i]) {  Return i;  }  }  Return -1;  }  //获取指定下标 pos 的值  Public int getPos (int pos) {  Int retVal = -1;  //检查 pos 是否合法  Try {  CheckGetPos (pos);  RetVal = elem[pos];  ;  } catch (PosIndexIllegalException e) {  e.getMessage ();  }  Return retVal;  }  //      删除第一次出现关键字 key 的方法  Public void remove (int key) {  //先获取第一次出现 key 元素的下标  Int index = indexOf (key);  If (index == -1) {  System.Out.Println ("没有找到你要删除的数据！");  Return;  }  For (int i = index; i < usedSize - 1; i++) {  Elem[i] = elem[i + 1];  }  UsedSize--;  }  /**  * removeAll 方法删除整个顺序表  */  Public void removeAll () {  Elem = new int[5];  UsedSize = 0;  }  //    判满方法  Private boolean isFull () {  Return usedSize == elem. Length;  }  //    判断顺序表的下标是否合法  Private void checkedAddPos (int pos) {  if (pos < 0 || pos > usedSize) {  Throw new PosIndexIllegalException ();  }  }  //   判断下标 pos 是否合法  Private boolean checkGetPos (int pos) {  if (pos < 0 || pos >= usedSize) {  Return false;  }  Return true;  }  /**  * 获取顺序表的个数  *  * @return 返回数组的大小  */  Public int size () {  Return usedSize;  }  }  Class PosIndexIllegalException extends RuntimeException {  Public PosIndexIllegalException () {  }  Public PosIndexIllegalException (String msg) {  Super (msg);  }  
}

🍔测试程序

我们是在外部的程序 MyArrayListTest 中进行的测试，先准备两个顺序表，然后调用 merge 方法，并把两个参数传进去，然后会返回一个顺序表，我们再继续调用我们封装的 MyArrayList 类当中的 display 方法。

Package TextReport;  Public class MyArrayListTest {  Public static void main (String[] args) {  //准备两个顺序表（非递减的顺序表）  MyArrayList myArrayList 1 = new MyArrayList ();  MyArrayList 1.Add (1);  MyArrayList 1.Add (5);  MyArrayList 1.Add (10);  MyArrayList 1.Add (13);  MyArrayList 1.Display ();  ;  MyArrayList myArrayList 2 = new MyArrayList ();  MyArrayList 2.Add (6);  MyArrayList 2.Add (11);  MyArrayList 2.Add (12);  MyArrayList 2.Add (33);  MyArrayList 2.Add (44);  MyArrayList 2.Add (47);  MyArrayList 2.Add (52);  MyArrayList 2.Add (66);  MyArrayList 2.Display ();  ;  //调用 merge 方法  MyArrayList mergeArrayList = merge (myArrayList 1, myArrayList 2);  //调用 display 方法  MergeArrayList.Display ();  }  /**  * 合并两个升序的非递减顺序表，并返回新的合成的顺序表  *  * @param list 1 按值非递减顺序表一  * @param list 2 按值非递减顺序表二  * @return 返回一个新的合并了的链表  */  Public static MyArrayList merge (MyArrayList list 1, MyArrayList list 2) {  MyArrayList newList = new MyArrayList (50);  Int i = 0, j = 0;  While (i < list 1.Size () && j < list 2.Size ()) {  If (list 1. Elem[i] < list 2. Elem[j]) {  NewList. Elem[newList. UsedSize] = list 1. Elem[i];  I++;  NewList. UsedSize++;  } else {  NewList. Elem[newList. UsedSize] = list 2. Elem[j];  J++;  NewList. UsedSize++;  }  }  While (i < list 1.Size ()) {  NewList. Elem[newList. UsedSize] = list 1. Elem[i];  I++;  NewList. UsedSize++;  }  While (j < list 2.Size ()) {  NewList. Elem[newList. UsedSize] = list 2. Elem[j];  NewList. UsedSize++;  J++;  }  Return newList;  }  
}