数据结构与算法-合并有序数组

习题：实现两个整型有序数组合并为一个有序数组

这是LeetCode上的编号88的题目。

题目前提条件是有序数组a当前存储元素个数m，和有序数组b当前存储元素个数n，而数组a实际存储空间可以存储(m+n)个元素，现需要将数组b合并到数组a，合并后仍旧是有序数组。

我想到的方法就是申请一个两个数组存储元素个数总和的临时数组空间，将两个数组元素一一比较后插入临时数组。

具体实现如下：

int merge(int *a, int m, int *b, int n)
{
  int a_index = 0;
  int b_index = 0;
  int *tmp_array = NULL;
  int tmp_index = 0;
  
  // 省去入参检查
  tmp_array = malloc((m+n) * sizeof(int));
  if (NULL == tmp_array)
  {
    printf("%s %s %d    \n", __FILE__, __func__, __LINE__ );
    return -1;
  }

  // 记得初始化操作
  memset(tmp_array, 0, sizeof(int) * (m+n));

  while (a_index < m && b_index < n)
  {
    tmp_array[tmp_index++] = a[a_index] < b[b_index] ? a[a_index++] : b[b_index++];
  }

  while (a_index < m)
  {
    tmp_array[tmp_index++] = a[a_index++];
  }

  while (b_index < n)
  {
    tmp_array[tmp_index++] = b[b_index++];
  }

  memset(a, 0, (m+n) * sizeof(int));
  memcpy(a, tmp_array, (m+n) * sizeof(int));

  SAFE_FREE(tmp_array);
  
  return 0;
}

因为是LeetCode上的题目，所以去上面看了下官方解题，发现有三种方式，其中一种是将数组b拷贝到数组a后面再进行排序。另外还有一种则是通过从后往前比较，将比较大的直接存放到a数组的最后可用位置，这样就不需要申请新的内存。

我自己实现了下，如下：

int merge(int *a, int m, int *b, int n)
{
  int count = m + n - 1;
  int a_index = m - 1;
  int b_index = n - 1;
  
  // 省去入参坚持

  // 数组下标的边界条件一定要想清楚
  while (a_index >= 0 && b_index >= 0)
  {
    a[count--] = a[a_index] > b[b_index] ? a[a_index--] : b[b_index--];
  }

  while (a_index >= 0)
  {
    a[count--] = a[a_index--];
  }

  while (b_index >= 0)
  {
    a[count--] = b[b_index--];
  }

  return 0;
}

FEATURED TAGS