经典算法：双指针问题--数组合并

向右看齐 2023-03-01 09:57 28阅读 0赞

**算法—程序的灵魂，没错就是灵魂** ！

今天我们来聊聊关于双指针问题中的数组合并问题

> 内容参考：《你也能看得懂的Python算法书》  
> 转载请标注： https://blog.csdn.net/qq\_43582207  
> python版本：Python3.7  
> IDE：Jupyter notebook  
> 作者:My apologize

### 文章目录 ###

*  双指针问题
 *   *  数组合并
     *   *  1.合并有序数组

# 双指针问题 #

首先介绍一个概念：“指针”，他是编程语言中的一个对象，他存储着一个内存空间的地址，计算机可以通过这个地址找到变量值，这个特定的地址指向这个特定的值。优点在于可以有效利用零碎的内存空间。（不过python中没有指针的，以下涉及指针部分采用列表“模拟指针”来完成python中的指针问题）

## 数组合并 ##

### 1.合并有序数组 ###

指针是内存空间的地址，可以通过一个数组中每个元素的下标来找值，所以储存这个元素位置的下标值可以看作一个指针（“模拟指针”）  
有两个有序数组：  
l1 = \[1, 3, 4, 6, 10\]  
l2 = \[2, 5, 8, 11\]  
目的：将l1和l2合并为一个新的从小到大的数组

第一次比较将l2\[0\]和l1\[1\]进行比较，如果l2\[0\]比l1\[0\]大，就移动到下一个和l1\[1\]比较，以此类推。如果l2\[0\]比l1\[0\]小，就把l2\[0\]插在l1\[0\]位置上，后面元素依次向后移动。  
之后把l2\[1\]再进行比较，直到比完所有l2中的元素完成合并

**具体步骤：**  
1.初始化两个数组：

l1 = [1, 3, 4, 6, 10]
    l2 = [2, 5, 8, 11]

2.创建一个l1的副本ans（用于储存排序完成后的数组的变量）  
所有插入操作都是对ans，这样不会修改原有的l1

ans = l1.copy()

3.遍历l1的下标ind（存储数组中数值的下标的变量）

ind = 0

4.需要一个for循环对第二个数组l2实现从小到大的遍历

for i in range(0, len(l2)):

5.首先外循环i = 0，ind =0 ,l2第一个元素和l1的第一个元素比较，如果比它小则插入在l1第一个元素的后面，然后结束循环，换i=1;如果比它大就ind+1,让l2的第一个元素和l1第二个元素比较，重复之。  
程序：while循环如果l2\[0\] <= l1\[0\],则在ans中下标1的位置插入l2\[0\],然后跳出while循环，反之ind加1变成1，当ind的值等于l1的长度时也结束while循环。

while ind < len(l1):
            if l2[i] <= l1[ind]:
                ans.insert(ind + i, l2[i])
                break
            else:
                ind += 1

6.如果l2的元素一直比较到l1的最后一个元素，还是l2的元素比l1元素大，则说明这个l2元素比l1所有元素都大，因为l2是升序，所有之后的所有l2元素都大，直接拼接在l1元素后面就行，然后退出for循环

else:
            ans += l2[i:]
            break

以下是完整代码（可直接运行）：

l1 = [1, 3, 4, 6, 10]
    l2 = [2, 5, 8, 11]
    ind = 0
    ans = l1.copy()
    for i in range(0, len(l2)):
        while ind < len(l1):
            if l2[i] <= l1[ind]:
                ans.insert(ind + i, l2[i])
                break
            else:
                ind += 1
        else:
            ans += l2[i:]
            break
    print(ans)

运行结果：
    [1, 2, 3, 4, 5, 6, 8, 10, 11]

============================================================================

**python经典算法持续更新中，明天预告：二分查找**  
///感兴趣的朋友，点个关注，学习不迷路！///

发表评论取消回复

表情：

评论列表（有 0 条评论，28人围观）

还没有评论，来说两句吧...

相关阅读

相关【基础算法】——双指针算法

双指针算法的原理和实战

今天药忘吃喽~/ 2024年04月27日 07:35/ 0 赞/ 88 阅读

相关【算法】双指针

双指针双指针算法，通过设置两个变量不同方向同一方向，不同速度例如： [27. 移除元素 - 力扣（LeetCode）][27. _ - _Le

待我称王封你为后i/ 2024年03月27日 13:02/ 0 赞/ 85 阅读

相关算法：合并两个有序数组---双指针[1]

![在这里插入图片描述][901cb5a6d22247e4a1b2fcb20c6adfe5.png_pic_center] 1、题目：给你两个按非递减顺序排列的整

男娘i/ 2024年03月26日 23:14/ 0 赞/ 120 阅读

相关算法——双指针

一、背景知识 > 双指针（Two Pointers）：指的是在遍历元素的过程中，不是使用单个指针进行访问，而是使用两个指针进行访问，从而达到相应的目的。 >

- 日理万妓/ 2024年02月18日 13:03/ 0 赞/ 82 阅读

相关 leetcode 88.合并两个有序数组（双指针 java）

给定两个有序整数数组 nums1 和 nums2，将 nums2 合并到 nums1 中，使得 num1 成为一个有序数组。说明: 初始化 nums1 和 nums2 的

蔚落/ 2023年08月17日 17:01/ 0 赞/ 118 阅读

相关经典算法：双指针问题--二分查找

算法—程序的灵魂，没错就是灵魂！今天我们来聊聊关于双指针问题中的二分查找的问题 > 内容参考：《你也能看得懂的Python算法书》 > 转载请标注： https:/

怼烎@/ 2023年03月01日 11:53/ 0 赞/ 5 阅读

相关经典算法：双指针问题--数组合并

算法—程序的灵魂，没错就是灵魂！今天我们来聊聊关于双指针问题中的数组合并问题 > 内容参考：《你也能看得懂的Python算法书》 > 转载请标注： https://

向右看齐/ 2023年03月01日 09:57/ 0 赞/ 29 阅读

相关使用双指针合并两个有序数组

题目描述：给定两个有序数组nums1和nums2，请你将nums2合并到nums1中，使nums1成为一个有序数组。说明：初始化nums1和nums2

青旅半醒/ 2022年12月28日 11:22/ 0 赞/ 123 阅读

相关 559-双指针思想解决数组问题

将字符串逆序采用双指针的思想分别指向数组的首元素和末尾元素 ![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY

逃离我推掉我的手/ 2022年09月11日 10:11/ 0 赞/ 163 阅读

相关 559-双指针思想解决数组问题

将字符串逆序采用双指针的思想分别指向数组的首元素和末尾元素 ![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY

「爱情、让人受尽委屈。」/ 2022年08月28日 14:53/ 0 赞/ 158 阅读