[随缘一题]合并排序数组ii

Posted1 by 呼延十 on January 5, 2019 Hot:

来源

lintcode-6.合并排序数组 II

描述

合并两个排序的整数数组A和B变成一个新的数组。

样例

给出A=[1,2,3,4]B=[2,4,5,6],返回 [1,2,2,3,4,4,5,6]

解题思路

用两个指针指向两个数组,每次取较小的放入结果数组.

在某个数组全部加入结果后,将另一个数组的值全部加入结果数组.

实现代码

public int[] mergeSortedArray(int[] A, int[] B) {
  //定义新数组,长度等于两个数组织和
  int[] result = new int[A.length + B.length];
  //定义三个指针,指向两个输入数组和结果数组
  int i = 0, j = 0, h = 0;
  //当A,B都没有遍历完的时候
  while (i < A.length && j < B.length) {
    //取较小的一个加入结果数组,然后将该数组的指针后移,结果数组指针后移
    if (A[i] <= B[j]) {
      result[h] = A[i];
      i++;
    } else {
      result[h] = B[j];
      j++;
    }
    h++;
  }
  //分别遍历两个数组,将剩余数字加入结果数组中.
  //这里其实只会执行一个,因为从while循环中出来,必然有一个数组被遍历完了.
  for (; i < A.length; i++,h++) {
    result[h] = A[i];
  }
  for (; j < B.length; j++,h++) {
    result[h] = B[j];
  }
  //返回结果
  return result;
}

完。




ChangeLog

2019-01-05 完成

以上皆为个人所思所得,如有错误欢迎评论区指正。

欢迎转载,烦请署名并保留原文链接。

联系邮箱:huyanshi2580@gmail.com

更多学习笔记见个人博客——>呼延十