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

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

前言

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

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天】使用指针访问数组元素。
33 3
|
2月前
|
存储 编译器 C语言
数据结构-顺序表详解(看这篇就足够了,哈哈哈)
数据结构-顺序表详解(看这篇就足够了,哈哈哈)
56 2
|
1月前
使用指针访问数组元素
【10月更文挑战第31天】使用指针访问数组元素。
38 2
|
2月前
|
算法 程序员 索引
数据结构与算法学习七:栈、数组模拟栈、单链表模拟栈、栈应用实例 实现 综合计算器
栈的基本概念、应用场景以及如何使用数组和单链表模拟栈,并展示了如何利用栈和中缀表达式实现一个综合计算器。
38 1
数据结构与算法学习七:栈、数组模拟栈、单链表模拟栈、栈应用实例 实现 综合计算器
|
1月前
|
存储 算法 安全
2024重生之回溯数据结构与算法系列学习之顺序表【无论是王道考研人还真爱粉都能包会的;不然别给我家鸽鸽丢脸好嘛?】
顺序表的定义和基本操作之插入;删除;按值查找;按位查找等具体详解步骤以及举例说明
|
1月前
|
存储 C语言
【数据结构】顺序表(c语言实现)(附源码)
本文介绍了线性表和顺序表的基本概念及其实现。线性表是一种有限序列,常见的线性表有顺序表、链表、栈、队列等。顺序表是一种基于连续内存地址存储数据的数据结构,其底层逻辑是数组。文章详细讲解了静态顺序表和动态顺序表的区别,并重点介绍了动态顺序表的实现,包括初始化、销毁、打印、增删查改等操作。最后,文章总结了顺序表的时间复杂度和局限性,并预告了后续关于链表的内容。
65 3
|
1月前
|
算法 安全 NoSQL
2024重生之回溯数据结构与算法系列学习之顺序表习题精讲【无论是王道考研人还真爱粉都能包会的;不然别给我家鸽鸽丢脸好嘛?】
顺序表的定义和基本操作之插入;删除;按值查找;按位查找习题精讲等具体详解步骤以及举例说明
|
1月前
|
算法 索引
单链表题+数组题(快慢指针和左右指针)
单链表题+数组题(快慢指针和左右指针)
37 1
|
2月前
|
存储
如何使用指针数组来实现动态二维数组
指针数组可以用来实现动态二维数组。首先,定义一个指向指针的指针变量,并使用 `malloc` 为它分配内存,然后为每个子数组分配内存。通过这种方式,可以灵活地创建和管理不同大小的二维数组。
|
2月前
|
存储
如何通过指针数组来实现二维数组?
介绍了二维数组和指针数组的概念及其区别,详细讲解了如何使用指针数组模拟二维数组,包括定义与分配内存、访问和赋值元素、以及正确释放内存的步骤,适用于需要动态处理二维数据的场景。