两个非递减顺序表合并成一个非递减顺序表
- 引入
以下这个例题的描述是关于合并两个有序的数组，然后合并之后同样也是一个非递减的顺序排列
但是我名这里讲的不是顺序表，而是封装成一个顺序表，但是我们这里的顺序表其实底层同样是一个数组，所以解题的思路完全相同，我们接下来要讲的就是“两个非递减顺序表合成的一个非递减的顺序表”。
合并两个有序数组
给你两个按非递减顺序排列的整数数组 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; } }
🥰测试结果
💗图文并茂
该图片是合并结束之后的图示，可以形象的看清楚 i ，j，k 这三个“指针是如何“行走的”。
注意：k 下标其实是 usedSize，是顺序表中的用来表示顺序表的有效长度。
🎊视频演示
这个视频简单的演示了我当前举的这个例子是如何进行合并的过程，时常两分钟，希望可以看完，这样可以更好的理解 “如何合并两个非递减的顺序表”。
两个非递减顺序表合并视频演示
点赞+收藏+关注💕
