算法：合并两个有序整数数组

我就是我 2023-10-10 09:54 34阅读 0赞

**描述：** 有arr1，arr2两个已排序数组，设计算法，合并两个数组，并且合并后的数组仍是有序的  
不得使用已有的任何库函数或数据结构，只通过基本数组完成

以下的结构是O（n）=n^2,是不合适的

for(int i = 0;i<arr1.length:i++){
    	 		for(int j = 0;j <arr2.lenght;j++){
    	 	 //TODO
    			}
    	 }

请设计O（n）=n的算法。

--------------------

**PS:** 设计算法时，忽略了存在连续几个数都小于同一下标处某个数的情况，导致测试用例通过率并不是100%，后面发现了错误，直接PO上其他博主已有的代码，O（n）都是O（m+n）。

其他使用了已有数据结构的代码，如使用list，set，map等，暂不考虑。

**正确算法1:**  
来自：https://www.cnblogs.com/williamjie/p/9958285.html

public static int[] MergeList(int a[], int b[]) {
    		int result[];
    		// 定义一个新数组，长度为两个数组长度之和
    		result = new int[a.length + b.length];
    		// i:a数组下标 j：b数组下标 k：新数组下标
    		int i = 0, j = 0, k = 0;
    		// 按位循环比较两个数组，较小元素的放入新数组，下标加一（注意，较大元素对应的下标不加一），
    		直到某一个下标等于数组长度时退出循环
    		while (i < a.length && j < b.length)
    			if (a[i] <= b[j]) {
    				result[k++] = a[i++];
    			} else {
    				result[k++] = b[j++];
    			}
    		/*
    		 * 后面连个while循环是用来保证两个数组比较完之后剩下的一个数组里的元素能顺利传入 *
    		 * 此时较短数组已经全部放入新数组，较长数组还有部分剩余，最后将剩下的部分元素放入新数组
    		 */
    		while (i < a.length)
    			result[k++] = a[i++];
    		while (j < b.length)
    			result[k++] = b[j++];
    		return result;
    	}

**正确算法2：**  
来自：链接不详，来自leetcode题解区回答

class Solution {
        public void merge(int[] nums1, int m, int[] nums2, int n) {
            int p = m-- + n-- -1;
            while(m>=0 && n>=0)
                nums1[p--] = nums1[m] > nums2[n] ? nums1[m--] : nums2[n--];
            
            while(n>=0)
                nums1[p--] = nums2[n--];
        }
    }

**错误算法：**  
没有考虑连续几个数都比另一个数组中的数小的情况，如

int []arr1 = {1,3,35,64};
    		int []arr2 = {2,4,5,9,10,23};

这个测试样例就比较好，发现了算法设计中的错误。  
![在这里插入图片描述][20190924191442655.png]

public static int[] fun(int []arr1,int []arr2) {
    		int []temp = new int[arr1.length + arr2.length];
    		if(arr1.length <= arr2.length) {
    			int size2 = 0;//设置计数器，统计temp实际长度
    			for(int j = 0;j < arr1.length;j++) {
    				//arr1，arr2，同一下标处两两比较，小的放入temp第一位，大的随后
    				if(arr1[j] <= arr2[j]) {
    					temp[size2] = arr1[j];
    					size2++;
    					temp[size2] = arr2[j];
    					size2++;
    				}else {
    					temp[size2] = arr2[j];
    					size2++;
    					temp[size2] = arr1[j];
    					size2++;
    				}
    			}
    			//将剩余长度的已排序部分，直接放入temp
    			for(int k = size2/2;k < arr2.length;k++) {
    				temp[size2] = arr2[k];
    				size2++;
    				
    			}
    		}
    		//因为只是同一下标处交换了，没有比较后续位置，所以还存在错位现象：
    		//上面的例子，完成后应该是： 1 2 3 4 5 6 7 9 8 10 23，因为7 9 8三个数
    		//尽管有错位，但是错位只通过一次交换就能完成排序
    		for(int i = 0; i < temp.length-1;i++) {
    			if(temp[i] > temp [i+1]) {//异或运算，直接交换位置
    				temp[i] = temp[i]^temp[i+1];
    				temp[i+1] = temp[i]^temp[i+1];
    				temp[i] = temp[i]^temp[i+1]; 
    			}
    		}
    		return temp;
    	}

public static void main(String []args) {
    		int []arr1 = {1,3,6,7,8};
    		int []arr2 = {2,4,5,9,10,23};
    		System.out.println(fun(arr1, arr2).length);
    		for(int i:fun(arr1, arr2)) {
    			System.out.print(i+" ");
    		}
    	}

**正确测试结果：**  
第一组：  
![在这里插入图片描述][20190924183205909.png]  
第二组：  
![在这里插入图片描述][20190924183520614.png]  
第三组：  
![在这里插入图片描述][20190924192032852.png]

> 后记：欢迎各位读者提出见解，勘误！

[20190924191442655.png]: https://img-blog.csdnimg.cn/20190924191442655.png
[20190924183205909.png]: https://img-blog.csdnimg.cn/20190924183205909.png
[20190924183520614.png]: https://img-blog.csdnimg.cn/20190924183520614.png
[20190924192032852.png]: https://img-blog.csdnimg.cn/20190924192032852.png