两个有序数组合并成一个有序数组

可以使用双指针的方法，从两个数组的开头开始比较，每次取两个数组中较小的元素放入新的数组中，直到其中一个数组遍历完毕。然后将另一个数组中剩余的元素直接拼接到新数组的末尾即可。

示例代码：

def merge_sorted_arrays(nums1, nums2):
    m, n = len(nums1), len(nums2)
    i, j = 0, 0
    res = []
    while i < m and j < n:
        if nums1[i] < nums2[j]:
            res.append(nums1[i])
            i += 1
        else:
            res.append(nums2[j])
            j += 1
    res += nums1[i:]
    res += nums2[j:]
    return res

时间复杂度为 $O(m+n)$，空间复杂度为 $O(m+n)$。

相关问题

c语言将两个有序数组合并成一个有序数组

### 回答1：
可以使用归并排序的思想，将两个有序数组合并成一个有序数组。

具体步骤如下：

1. 定义三个指针，分别指向两个有序数组和合并后的数组。

2. 比较两个有序数组的当前元素大小，将较小的元素放入合并后的数组中，并将指针向后移动。

3. 如果其中一个数组已经遍历完了，将另一个数组中剩余的元素依次放入合并后的数组中。

4. 返回合并后的数组。

示例代码如下：

#include <stdio.h>

int* merge(int* nums1, int nums1Size, int* nums2, int nums2Size) {
    int* res = (int*)malloc(sizeof(int) * (nums1Size + nums2Size));
    int i = , j = , k = ;
    while (i < nums1Size && j < nums2Size) {
        if (nums1[i] < nums2[j]) {
            res[k++] = nums1[i++];
        } else {
            res[k++] = nums2[j++];
        }
    }
    while (i < nums1Size) {
        res[k++] = nums1[i++];
    }
    while (j < nums2Size) {
        res[k++] = nums2[j++];
    }
    return res;
}

int main() {
    int nums1[] = {1, 3, 5, 7};
    int nums2[] = {2, 4, 6, 8};
    int* res = merge(nums1, 4, nums2, 4);
    for (int i = ; i < 8; i++) {
        printf("%d ", res[i]);
    }
    printf("\n");
    free(res);
    return ;
}

### 回答2：
将两个有序数组合并成一个有序数组，是C语言中一个经典的问题。这个问题可以通过归并排序的思想来解决。

归并排序的思想是将一个大数组分成两个小数组，分别进行递归排序，然后将两个小数组归并成一个有序数组。这个过程可以使用指针来实现。

首先，我们需要定义三个指针，分别指向要合并的两个数组和最终的合并后的数组。然后，我们使用一个while循环，比较两个指针所指的值，将较小的值加入到最终的数组中，并将相应的指针后移。

最后，我们需要处理一些边界条件，例如当有一个数组已经全部加入到最终的数组中时，需要将另一个数组中剩余的部分直接加入到最终的数组中。

下面是一个可行的C语言代码：

void Merge(int *arrA, int n, int *arrB, int m, int *arrC)
{
int i, j, k;
i = j = k = 0;
while (i < n && j < m)
{
if (arrA[i] < arrB[j])
{
arrC[k] = arrA[i];
k++;
i++;
}
else
{
arrC[k] = arrB[j];
k++;
j++;
}
}
while (i < n)
{
arrC[k] = arrA[i];
k++;
i++;
}
while (j < m)
{
arrC[k] = arrB[j];
k++;
j++;
}
}

以上代码中，arrA和arrB是要合并的两个有序数组，n和m分别是这两个数组的长度，arrC是最终的合并后的有序数组。最后，我们可以使用下面的代码来测试函数是否正确：

int main()
{
int arrA[5] = {1,3,5,7,9};
int arrB[5] = {2,4,6,8,10};
int arrC[10];
Merge(arrA, 5, arrB, 5, arrC);
for (int i = 0; i < 10; i++)
{
printf("%d ", arrC[i]);
}
return 0;
}

运行结果为：1 2 3 4 5 6 7 8 9 10。

可以看到，我们成功地将两个有序数组合并成了一个有序数组。

### 回答3：
在C语言中，将两个有序数组合并成一个有序数组需要用到额外的空间来存储结果数组。

首先，我们需要定义两个有序数组和一个结果数组：

int arr1[] = {1, 3, 5, 7, 9};
int arr2[] = {2, 4, 6, 8, 10};
int n1 = sizeof(arr1) / sizeof(arr1[0]);
int n2 = sizeof(arr2) / sizeof(arr2[0]);
int newArr[n1 + n2];

接着，我们可以使用两个指针分别指向两个数组的开头，然后比较两个指针所指向的元素，将较小的元素加入结果数组，并将指向该元素的指针向后移动。重复这个过程直到其中一个数组的所有元素都加入结果数组：

int i = 0, j = 0, k = 0;
while (i < n1 && j < n2) {
    if (arr1[i] < arr2[j]) {
        newArr[k] = arr1[i];
        i++;
    } else {
        newArr[k] = arr2[j];
        j++;
    }
    k++;
}

如果其中一个数组的所有元素已经加入结果数组，我们需要将另一个数组中剩余的元素依次加入结果数组：

while (i < n1) {
    newArr[k] = arr1[i];
    i++;
    k++;
}

while (j < n2) {
    newArr[k] = arr2[j];
    j++;
    k++;
}

最后，我们得到的newArr数组就是合并后的有序数组。完整代码如下：

#include <stdio.h>

int main() {
    int arr1[] = {1, 3, 5, 7, 9};
    int arr2[] = {2, 4, 6, 8, 10};
    int n1 = sizeof(arr1) / sizeof(arr1[0]);
    int n2 = sizeof(arr2) / sizeof(arr2[0]);
    int newArr[n1 + n2];

    int i = 0, j = 0, k = 0;
    while (i < n1 && j < n2) {
        if (arr1[i] < arr2[j]) {
            newArr[k] = arr1[i];
            i++;
        } else {
            newArr[k] = arr2[j];
            j++;
        }
        k++;
    }

    while (i < n1) {
        newArr[k] = arr1[i];
        i++;
        k++;
    }

    while (j < n2) {
        newArr[k] = arr2[j];
        j++;
        k++;
    }

    printf("New array: ");
    for (int i = 0; i < n1 + n2; i++) {
        printf("%d ", newArr[i]);
    }
    printf("\n");

    return 0;
}

js怎么把两个有序数组合并成一个有序数组

可以使用归并排序的思想，将两个有序数组合并成一个有序数组。具体做法是创建一个新的数组，依次比较两个有序数组的元素大小，将较小的元素放入新数组中，直到其中一个数组遍历完毕，然后将另一个数组中剩余的元素放入新数组中。下面是一个示例代码：

function mergeSortedArray(arr1, arr2) {
  let i = 0, j = 0;
  const mergedArr = [];
  while (i < arr1.length && j < arr2.length) {
    if (arr1[i] <= arr2[j]) {
      mergedArr.push(arr1[i]);
      i++;
    } else {
      mergedArr.push(arr2[j]);
      j++;
    }
  }
  if (i < arr1.length) {
    mergedArr.push(...arr1.slice(i));
  }
  if (j < arr2.length) {
    mergedArr.push(...arr2.slice(j));
  }
  return mergedArr;
}

这个函数接受两个有序数组 `arr1` 和 `arr2`，返回合并后的有序数组。其中使用了 `while` 循环和两个指针 `i` 和 `j` 遍历两个数组，使用 `if` 条件判断比较大小，将较小的元素放入新数组中。最后使用 `slice` 函数将剩余的元素放入新数组中。