将两个数组合并排序

1. 将两个数组合并排序

public void MergeTwoArray() {
        int i = 0;
        int j = 0;
        int k = 0;
        int[] nums1 = new int[] {1,2,3,0,0,0};
        int[] nums2 = new int[] {2,5,6};
        int[] num = new int[nums1.length + nums2.length];
        while (i < nums1.length && j < nums2.length) {
            if (nums1[i] < nums2[j]) {
                num[k++] = nums1[i++];
            } else {
                num[k++] = nums2[j++];
            }
        }
        while (i < nums1.length) {
            num[k++] = nums1[i++];
        }
        while (j < nums2.length) {
            num[k++] = nums2[j++];
        }
        System.out.println(Arrays.toString(num));
    }

【文章参考】int类型的两个数组合并排序

2. 合并两个数组 三种解法

import java.util.Arrays;

import java.util.LinkedList;
/**
 * 合并两个数组      
 * int a[]={0,1,5,6,7,9,14};
 * int b[]={2,4,8,10,13};
 */
public class MergeTwoArray {
	//方法一：
	  private static void method1(int a[],int b[],int array[]) {
		//建立c数组，并将a添加进去  
		int c[]= Arrays.copyOf(a, a.length+b.length);
		//将b数组添加到已经含有a数组的c数组中去
		System.arraycopy(b, 0, c, a.length, b.length);
        //对c数组进行排序
		Arrays.sort(c);
        System.out.println("方法一：");
		for (int i = 0; i < c.length; i++) {
			System.out.print(c[i]+" ");
		}
	}
	 
	  //方法二:集合方法  使用LinkedList 队列
	  private static void method2(int array[],LinkedList<Integer> queue_a,LinkedList<Integer> queue_b ) {
		 //每循环一次，添加一个最小元素进入arrays
		  for (int i = 0; i < array.length; i++) {
			  //两个队列都不为空时，谁小取出谁
			 if (!queue_a.isEmpty()&&!queue_b.isEmpty()) {
				  if (queue_a.peek()<queue_b.peek()) {
					  array[i]=queue_a.poll();
					  continue;
				}else {
					array[i]=queue_b.poll();
					continue;
					}
			}
			 //当数组a为空时，取数组b的元素
				  if (queue_a.isEmpty()&&!queue_b.isEmpty()) {
					array[i]=queue_b.poll();
					continue;
				}
			 //当数组b为空时，取数组a的元素	  
				  if (queue_b.isEmpty()&&!queue_a.isEmpty()) {
					array[i]=queue_a.poll();
					continue;
				}
		}
		System.out.println("方法二：");
		for (int i = 0; i < array.length; i++) {
			System.out.print(array[i]+" ");
		}
	}
	
	 //方法三：递归方法
	  private static int [] method3(int a[],int a_start,int b[],int b_start,int array[],int array_start) {
		   
		   //若数组a中的元素都已经放到array数组中，而数组b未全部放到array中，
		   //那么将b中剩余的元素放到array中
           if (a_start>=a.length) {
              	for (int i = array_start; i < array.length; i++) {
					array[array_start]=b[b_start++];
				}
              	return array;
           }
           //若数组b中的元素都已经放到array数组中，而数组a未全部放到array中，
		   //那么将a中剩余的元素放到array中
           if (b_start>=b.length) {
			   for (int i = array_start; i < array.length; i++) {
				    array[array_start]=a[a_start++];
			}
			   return array;
		   }   	
           //将数组的头元素,b数组头元素 中的最小值赋予给array
           if (a[a_start]<b[b_start]) {
			  array[array_start]=a[a_start];
		     return	  method3(a, a_start+1, b, b_start,  array, array_start+1);
		   }else {
			   array[array_start]=b[b_start];
		     return	  method3(a, a_start, b, b_start+1, array, array_start+1); 
		    }
           
		}	
           
	
      public static void main(String[] args) {
		int a[]={0,1,5,6,7,9,14};
		int b[]={2,4,8,10,13};
		LinkedList<Integer> queue_a=new LinkedList<>();
		for (int i = 0; i < a.length; i++) {
			queue_a.offer(a[i]);
		}
		LinkedList<Integer> queue_b=new LinkedList<>();
		for (int i = 0; i < b.length; i++) {
			queue_b.offer(b[i]);
		}
		int array[]=new int[a.length+b.length];
		
		method1(a, b, array);
		System.out.println();
		method2(array, queue_a, queue_b);
		System.out.println("\n方法三：");
		int all[]=method3(a, 0, b, 0, array, 0);
		for (int i : all) {
			System.out.print(i+" ");
		}	
	}
} 

【文章参考】java合并两个数组三种解法

3. LeetCode88 合并两个有序数组

给定两个有序整数数组 nums1 和 nums2，将 nums2 合并到 nums1 中，使得 num1 成为一个有序数组。

说明:

• 初始化 nums1 和 nums2 的元素数量分别为 m 和 n。

• 可以假设 nums1 有足够的空间（空间大小大于或等于 m + n）来保存 nums2 中的元素。

示例:

输入:
nums1 = [1,2,3,0,0,0], m = 3
nums2 = [2,5,6], n = 3

输出: [1,2,2,3,5,6]

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/merge-sorted-array

---

题解

合并两个有序数组

---

方法一 : 合并后排序

最朴素的解法就是将两个数组合并之后再排序。该算法只需要一行(Java是2行)，时间复杂度较差，为O((n+m)log(n+m))。这是由于这种方法没有利用两个数组本身已经有序这一点。

实现

class Solution {
 public void merge(int[] nums1, int m, int[] nums2, int n) {
 System.arraycopy(nums2, 0, nums1, m, n);
 Arrays.sort(nums1);
 }
}

复杂度分析

时间复杂度 : O((n+m)log(n+m))
空间复杂度 : O(1)

方法二 : 双指针 / 从前往后

一般而言，对于有序数组可以通过 双指针法 达到O(n + m)O(n+m)的时间复杂度。

最直接的算法实现是将指针p1置为 nums1的开头，p2 为 nums2 的开头，在每一步将最小值放入输出数组中。

由于 nums1 是用于输出的数组，需要将 nums1 中的前m个元素放在其他地方，也就需要 O(m) 的空间复杂度。

实现

class Solution {
  public void merge(int[] nums1, int m, int[] nums2, int n) {
    // Make a copy of nums1.
    int [] nums1_copy = new int[m];
    System.arraycopy(nums1, 0, nums1_copy, 0, m);

    // Two get pointers for nums1_copy and nums2.
    int p1 = 0;
    int p2 = 0;

    // Set pointer for nums1
    int p = 0;

    // Compare elements from nums1_copy and nums2
    // and add the smallest one into nums1.
    while ((p1 < m) && (p2 < n))
      nums1[p++] = (nums1_copy[p1] < nums2[p2]) ? nums1_copy[p1++] : nums2[p2++];

    // if there are still elements to add
    if (p1 < m)
      System.arraycopy(nums1_copy, p1, nums1, p1 + p2, m + n - p1 - p2);
    if (p2 < n)
      System.arraycopy(nums2, p2, nums1, p1 + p2, m + n - p1 - p2);
  }
}

复杂度分析

时间复杂度 : O(n + m)
空间复杂度 : O(m)

方法三 : 双指针 / 从后往前

直觉

方法二已经取得了最优的时间复杂度O(n + m)，但需要使用额外空间。这是由于在从头改变nums1的值时，需要把nums1中的元素存放在其他位置。

如果我们从结尾开始改写 nums1 的值又会如何呢？这里没有信息，因此不需要额外空间。

这里的指针p 用于追踪添加元素的位置。

实现

class Solution {
  public void merge(int[] nums1, int m, int[] nums2, int n) {
    // two get pointers for nums1 and nums2
    int p1 = m - 1;
    int p2 = n - 1;
    // set pointer for nums1
    int p = m + n - 1;

    // while there are still elements to compare
    while ((p1 >= 0) && (p2 >= 0))
      // compare two elements from nums1 and nums2 
      // and add the largest one in nums1 
      nums1[p--] = (nums1[p1] < nums2[p2]) ? nums2[p2--] : nums1[p1--];

    // add missing elements from nums2
    System.arraycopy(nums2, 0, nums1, 0, p2 + 1);
  }
}

作者：LeetCode
转载链接：来源：力扣（LeetCode）