【初阶数据结构】——双“指针”求解顺序表(数组)常见问题

简介: 【初阶数据结构】——双“指针”求解顺序表(数组)常见问题

前言

这篇文章,我们一起来看几道数组相关的面试题。

158369d674d34dcb993697591cac5dc4.png

每道题目,我们给出的解题思路可能都不止一种,我们要不断分析讨论,找出最优的解题思路来实现

一起来看看吧!!!

题目1:移除元素

题目链接放在这里,供大家练习:链接: link

先来看一下题目吧:

ba73edb6d0704668bd3263f429db35d8.png

题目是什么意思呢?


其实就是给我们一个数组,还有一个值val,我们要删除这个数组中所有值和val相等的元素,然后返回删除之后的新数组的长度。


那怎么解决呢?接下来我们一起来分析一下:


思路1:暴力求解

思路1就是暴力求解,这也是我们可能最先会想到的一个方法:从头到尾找一个删除一个。


怎么做呢?


从数组的第一个元素开始,向后遍历,如何当前元素的值等于val的值,就删除。

怎么删呢?

将后面的元素,依次向前移动,将要删除的元素覆盖掉。后面也是如此,直至将数组中所有值等于val的元素都删除掉,就完成了。


那大家思考一下,这个方法好不好?


肯定是不太好的,如果给的数组中有大部分元素的值都等于val,比如像这样:

3713fa9bb33d461ca04cd1149f936f30.png

val的值是2,数组中所有等于2的元素,都要删除,每次删除都要挪动数据,等于val的元素越多,挪动的次数就越多,有些数据就会被不断地,重复的挪动,这样它的时间复杂度其实可以认为是O(N^2),效率就可能会比较低。

6e59c55d07a14d1a8b4ed53aeb7db782.png

那这种方法我们就不实现了,我们再思考思考有没有更优的解法。


思路2:空间换时间

第一中解法暴力求解,它的时间复杂度太大了,那有没有更好的方法呢?


这里提供一种空间换时间的解法。


具体思路是这样的:


我们再额外创建一个数组,假设命名为tmp,然后对原数组进行遍历,如果当前元素不等于val,就把他拷贝到tmp数组中,如果等于val,不做处理,这样遍历结束,tmp数组中放的就是删除之后的元素,然后我们把tmp中的元素再拷贝回原数组,tmp的大小就是要返回的新长度。

4d71c7692f1646259a849993d5ce13de.png


那这种思路,它的**时间复杂度就是就是O(N)**了,与第一种方法的O(N^2)相比,就好很多了。

但它的的缺点在于:

我们又额外开辟了一个数组,该数组的大小与原数组等大,因此它的空间复杂度也是O(N)。这是他不好的地方。

而且呢,题目也要求:

9c7ebc1a332a4c54b664abed22b6ca65.png

所以,这还没有完,我们要继续优化,找出一个即效率高,还不用开辟额外空间的算法。

那有没有这样的解法呢?

当然有,其实我们对解法2再稍做优化,就行了。

思路3:双指针原地删除(解法2的再优化)

其实思路还是2的思路,只不过这次我们不再另外开辟一个新的数组了。

那要怎么搞呢?

思路分析

这里我们定义两个变量作为两个指针(注意这里说的指针只是一个形象化的称谓,不是用来存储地址的指针变量),开始它们都指向0下标的位置。

151b867414074698b6d7b508f1f35bda.png

然后呢:


我们src指向的元素和val比较,如果不相等,就把src指向的元素赋值给dest指向的元素,即nums[dest]=nums[src],然后让dest和src都++。

然后再让src指向的元素和val比较,不相等继续上述操作,如果相等了,我们只让src++往后走,dest不动,然后再让src指向的元素和val比较,看是否等于val。

直至遍历完整个数组。

9c3a19dd9421455e8635ff6b39f1438e.png

f446976e7b934f73936f99b5c5202aa1.png

代码实现

那现在思路理清了,图也画出来了,接下来写代码就很简单了:

直接上代码:

int removeElement(int* nums, int numsSize, int val){
    int src=0;
    int dest=0;
    while(src<numsSize)
    {
        if(nums[src]!=val)
        {
            nums[dest++]=nums[src++];
        }
        else
        {
            src++;
        }
    }
    return dest;
}

0d5d8b6b42684ed2b7f26695c60a4218.png

题目2:删除有序数组中的重复项

链接分享给大家:链接: link

一起看一下题:

b87e569946674c8ba749000661dbb56d.png

这道题呢,其实就是让我们去重,数组中有些值重复出现,我们要让所有的元素都只出现一次,最终还是返回新数组长度。

这道题怎么做呢?

比较简单的一种方法还是利用双指针来解决。

思路:双指针

那这个题该如何利用双指针求解呢?

首先,还是定义两个变量作为指针,初始都指向下标为0位置。

dd7caf6ba6744d4a8935eddb6d21832d.png

如果两指针指向的元素相等,我们只让 src++往后走,过滤掉重复值。

2d67a9299e70427d85a4096220a9f3fa.png

如果不再相等,先让dest++,让后把src指向的元素赋值给dest指向的元素,然后再让src++。

5d5506def47245cc841e84cf3a91ab18.png

然后再判断两指针指向的元素是否相等,重复上述操作,直至src遍历完数组。

c7bd24117cf1460aa912411af004149d.png

最终dest+1就是去重后的数组长度。

代码实现

上代码:

int removeDuplicates(int* nums, int numsSize){
    int src=0;
    int dest=0;
    while(src<numsSize)
    {
        if(nums[src]==nums[dest])
        {
            src++;
        }
        else
        {
            // dest++;
            // nums[dest]=nums[src];
            // src++;
            nums[++dest]=nums[src++];
        }
    }
    return dest+1;
}

3da5cd3a44fa40cca5e87049504c9e8f.png

题目3:合并两个有序数组

链接: link

e9036e9b75014c1c9e301f398459c8d0.png

常规合并方法

首先我们思考一下,如果给我们两个非递减的数组,我们如何去合并它们。

其实用双指针的方法还可以搞定,举个例子:

假如现在有这样两个数组:

1b65671b0836401dbd1fa69174f7e418.png

如何合并?

两个指针分别指向两数组第一个元素,再开辟一个新数组,对他们进行比较,依次取较小的那个元素放到新数组中,如果相等,任选一个放入。

0fd35bdfec4d4d08b6fe83cdb6e2753d.png

但是,对于这个题,这种方法可行吗?

显然是不可行的。

题目分析

为什么不可行呢?

我们来看这道题:

81e21b1fc1804459a9ca8b2acdccd84b.png它给我们两个按 非递减顺序 排列的整数数组 nums1 和 nums2,确定是要求我们,但是要求我们把合并后的数组放到nums1 中

也就是说,nums1 提前把空间开好了,已经足够放得下合并之后的整个数组了,不需要我们再额外开辟新数组了。

那上面那种方法显然就不适用了。

那这种情况我们应该怎么搞呢?

就拿题中这个例子来看:

da89ee71ad62404e9287bb97ae2f493a.png

如果我们还像上面那样从前往后两两比较大小,还可以吗?

如果nums2的的第一个元素就比nums1的小,那题目要求放到

nums1里,这样是不是就把nums2的第一个元素覆盖掉了啊。

所以这样搞不行。

那应该怎么办呢?

927f25794bd54d0f9f6b21e7dc3be21a.png

我们知道,nums1已经提前开好了多余的空间,这些空间在哪里啊,是在nums1有效数据的后面

思路:三指针

所以我们怎么做比较好?

是不是从后往前倒着比较啊。

怎么比?

要取出两者中较大的元素放到后面,后面的数据我们覆盖掉是没问题的。

那接下来我来画图带大家再梳理一下思路:

这里需要我们再增加一个指针。

815de226df1645cdbd7b9ecffc3d6e47.png

指针i1,i2分别指向数组nums1和nums2的最后一个元素,注意nums1是有效数据的最后一个,然后加一个dest指向nums1的最后一个位置。

然后开始比较:

i1,i2指向的元素哪个大,就把该元素赋值给dest指向的元素,然后dest和对应的i1或i2向前移动一个位置,继续比较。

1d5eb42082da4b1396cc718b09f1ae02.png

相等的话,我们随便给哪一个都行

我这里就选择把i1指向的值给dest。

f6334dbc9cdf4ae1aeef3017c7085b55.png

这一步的代码就是这样:

04bc7a5f33f6400e8a5af954d0f70b3e.png

然后继续走:

走到这个位置我们发现


73544e3de53e4764b7486713f357bf2b.png

i2就走完了,遍历结束了,那此时是不是就完成了啊

2eaae2f22a144566958a3a22b388bedf.png

这就是最终的状态了。

所以:

如果是i2先走完,i2走完就结束了,完成了。因为这些元素本来就在nums1中,不需要动了。

那也有可能是i1先走完啊,i1先走完是不是也直接结束了呢?我们来分析一下:

看这种情况:

452c726407144c078cc19640a24e30d5.png

还是按上面的方法依次进行比较。

但是这次我们会发现:

997cfbcafb384615bb90baa8acd097ed.png

这次是i1先走完,但是这样结束了吗。

还没有,

我们需要把nums2中剩下的元素再拷贝到nums1前面的位置。

所以要注意:

如果是i1先走完,我们还需要继续处理,把nums2中剩余的元素放到nums1中。

2e0adfc946594fa2bfc66e099fea90e5.png

代码实现

所以最终代码应该是这样的

void merge(int* nums1, int nums1Size, int m, int* nums2, int nums2Size, int n){
    int i1=m-1;
    int i2=n-1;
    int dest=m+n-1;
    while(i1>=0&&i2>=0)
    {
        if(nums2[i2]>=nums1[i1])
        {
            nums1[dest--]=nums2[i2--];
        }
        else
        {
            nums1[dest--]=nums1[i1--];
        }
    }
    while(i2>=0)
    {
        nums1[dest--]=nums2[i2--];
    }
}

再简单解释一下,相信大家就能很好的理解了:

首先说一下,题目里给的参数有些冗余

127953cfed6142d9a9add843aec0d800.png

nums1Size和nums2Size其实不要也可以,因为nums1Size就是m+n,nums2Size就是n。

然后代码也简单提一下:

24658606f14f405683fa90a1ddf3ad5e.png

所以最终的代码就是这样。

7bde791d975a4b1bba10058dc6908ba5.png

好了,以上就是几个数组相关面试题的讲解,欢迎大家指正!!!

ca468e0f153a4e2285eb4830deb1a762.png

目录
相关文章
|
1月前
使用指针访问数组元素
【10月更文挑战第30天】使用指针访问数组元素。
38 3
|
1天前
|
数据库
数据结构中二叉树,哈希表,顺序表,链表的比较补充
二叉搜索树,哈希表,顺序表,链表的特点的比较
数据结构中二叉树,哈希表,顺序表,链表的比较补充
|
27天前
|
存储 缓存 算法
在C语言中,数据结构是构建高效程序的基石。本文探讨了数组、链表、栈、队列、树和图等常见数据结构的特点、应用及实现方式
在C语言中,数据结构是构建高效程序的基石。本文探讨了数组、链表、栈、队列、树和图等常见数据结构的特点、应用及实现方式,强调了合理选择数据结构的重要性,并通过案例分析展示了其在实际项目中的应用,旨在帮助读者提升编程能力。
53 5
|
27天前
|
存储 程序员 编译器
C 语言数组与指针的深度剖析与应用
在C语言中,数组与指针是核心概念,二者既独立又紧密相连。数组是在连续内存中存储相同类型数据的结构,而指针则存储内存地址,二者结合可在数据处理、函数传参等方面发挥巨大作用。掌握它们的特性和关系,对于优化程序性能、灵活处理数据结构至关重要。
|
1月前
|
存储 C语言 计算机视觉
在C语言中指针数组和数组指针在动态内存分配中的应用
在C语言中,指针数组和数组指针均可用于动态内存分配。指针数组是数组的每个元素都是指针,可用于指向多个动态分配的内存块;数组指针则指向一个数组,可动态分配和管理大型数据结构。两者结合使用,灵活高效地管理内存。
|
1月前
|
容器
在使用指针数组进行动态内存分配时,如何避免内存泄漏
在使用指针数组进行动态内存分配时,避免内存泄漏的关键在于确保每个分配的内存块都能被正确释放。具体做法包括:1. 分配后立即检查是否成功;2. 使用完成后及时释放内存;3. 避免重复释放同一内存地址;4. 尽量使用智能指针或容器类管理内存。
|
1月前
|
存储 NoSQL 编译器
C 语言中指针数组与数组指针的辨析与应用
在C语言中,指针数组和数组指针是两个容易混淆但用途不同的概念。指针数组是一个数组,其元素是指针类型;而数组指针是指向数组的指针。两者在声明、使用及内存布局上各有特点,正确理解它们有助于更高效地编程。
|
1月前
|
存储 人工智能 算法
数据结构实验之C 语言的函数数组指针结构体知识
本实验旨在复习C语言中的函数、数组、指针、结构体与共用体等核心概念,并通过具体编程任务加深理解。任务包括输出100以内所有素数、逆序排列一维数组、查找二维数组中的鞍点、利用指针输出二维数组元素,以及使用结构体和共用体处理教师与学生信息。每个任务不仅强化了基本语法的应用,还涉及到了算法逻辑的设计与优化。实验结果显示,学生能够有效掌握并运用这些知识完成指定任务。
57 4
|
1月前
使用指针访问数组元素
【10月更文挑战第31天】使用指针访问数组元素。
48 2
|
1月前
|
存储 算法 安全
2024重生之回溯数据结构与算法系列学习之顺序表【无论是王道考研人还真爱粉都能包会的;不然别给我家鸽鸽丢脸好嘛?】
顺序表的定义和基本操作之插入;删除;按值查找;按位查找等具体详解步骤以及举例说明