合并有序数组

合并有序数组是指将两个已经有序的数组合并成一个有序的数组。这个问题可以使用双指针算法来解决。

具体实现方法如下：

1. 定义一个新的数组result，用于存放合并后的有序数组。

2. 定义两个指针i和j，分别指向两个有序数组的起始位置。

3. 依次比较两个数组中的元素大小，将较小的元素添加到result数组中，并将对应的指针向后移动一位。

4. 当其中一个数组的元素全部添加到result数组中后，将另一个数组中剩余的元素添加到result数组中。

5. 返回result数组。

下面是一个示例代码：

def merge_sorted_arrays(arr1, arr2):
    i, j = 0, 0
    result = []

    while i < len(arr1) and j < len(arr2):
        if arr1[i] < arr2[j]:
            result.append(arr1[i])
            i += 1
        else:
            result.append(arr2[j])
            j += 1

    # 将剩余的元素添加到result数组中
    result += arr1[i:]
    result += arr2[j:]

    return result

该算法的时间复杂度为O(m + n)，其中m和n分别为两个有序数组的长度。

相关问题

代码实现合并有序数组

好的，以下是合并有序数组的代码实现（假设两个数组已经有序）：

def merge_sorted_arrays(arr1, arr2):
    merged_arr = []
    i = j = 0
    
    while i < len(arr1) and j < len(arr2):
        if arr1[i] < arr2[j]:
            merged_arr.append(arr1[i])
            i += 1
        else:
            merged_arr.append(arr2[j])
            j += 1
            
    while i < len(arr1):
        merged_arr.append(arr1[i])
        i += 1
        
    while j < len(arr2):
        merged_arr.append(arr2[j])
        j += 1
        
    return merged_arr

首先，我们定义了一个名为 `merge_sorted_arrays` 的函数，它接收两个有序数组 `arr1` 和 `arr2` 作为参数。

接下来，我们创建了一个名为 `merged_arr` 的空数组，并定义了两个变量 `i` 和 `j`，它们分别代表 `arr1` 和 `arr2` 的索引。

然后，我们使用 while 循环遍历两个数组，比较当前索引的元素大小，并将较小值添加到 `merged_arr` 中。如果其中一个数组已经遍历完了，我们就使用另一个 while 循环将剩余的元素添加到 `merged_arr` 中。

最后，我们返回 `merged_arr`，即合并后的有序数组。

希望这个代码能够解决你的问题！

合并有序数组时间复杂度

合并两个有序数组的时间复杂度是O(n)，其中n是两个数组元素的总数量。如果要合并更多的有序数组，可以先依次合并前两个数组，再将结果与第三个数组合并，以此类推。每次合并的时间复杂度都是O(n)，因此合并k个有序数组的时间复杂度为O(knlogk)，其中logk是因为每次合并都可以将k个数组的数量减半，直到最后只剩一个数组。