C语言经典顺序表真题演练讲解
目录
- 1、移除元素
- 2、删除有序数组中的重复项
- 3、合并两个有序数组
1、移除元素
链接直达：
https://leetcode-cn.com/problems/remove-element/
题目：
思路：
法一：依次挪动数据进行覆盖
从第一个数据开始进行依次遍历，如同示例1，依次遍历数组，找到移除的元素2就把后面的数据往前挪动进行覆盖，如图所示：
此法有个缺陷，题目中明确指出使用空间复杂度O(1)的方法解决此问题，而此法的空间复杂度刚好为O(1)，可以解决，不过考虑周全些，时间复杂度在情况最坏时为O(N^2)，出现全是val的情况，将会挪动n-1+n-2+……出现了等差数列，时间复杂度为O(N^2)，此法不是最优，换。
法二：双指针1.0
依次遍历原数组，看是不是val，把不是val的值，拷贝到新数组，此法的时间复杂度是O(N)，空间复杂度也是O(N)，可是题目明确指出空间复杂度要为O(1)，所以此法不行，但是仔细想想，如果继续用此法双指针，但是不另开数组，就在原数组上改动可否呢？，由此引出双指针2.0
法三：双指针2.0
此法是在法二的基础上进行的升级，法二需要开辟额外数组，此法直接原数组改动。首先定义两个变量src和dst为0，都作为数组nums的下标，依次遍历src看nums[src]是否为val，若不是，将其赋给下标dst，再src++，dst++。若nums[src]=nums[dst]，则只把src++，dst不动，最后再把长度dst返回即可。
代码如下：
int removeElement(int* nums, int numsSize, int val){
int dst=0;
int str=0;
while(str<numsSize)
{
if(nums[str]==val)
{
str++;
}
else
{
nums[dst]=nums[str];
dst++;
str++;
}
}
return dst;
}
2、删除有序数组中的重复项
链接直达：
https://leetcode-cn.com/problems/remove-duplicates-from-sorted-array/
题目：
思路：
双指针（不额外开数组）
此题和上题类似，同样可以采用双指针，并在原数组进行改动，只需要定义两个变量dst和src作为数组nums的下标，但此时做出小变动，把src从下标1开始，而dst从下标0开始。让nums[src]每次和它前一个也就是nums[src-1]相比较，如果相等，则src++，若不等就把nums[src-1]赋给nums[dst]，再dst++，src++。
注意：
执行完上述操作后，还存在一个问题，那就是没把src的最后一个下标的值放到nums[dst]里头去，就如同本题的示例，当src走到倒数第二个值3的时候，和前一个3相等，此时需要++src，现在nums[src]就是4，和前一个值不相等，把3赋给nums[dst]，此时src再++到空了，没有数据和4比较了，越界，所以4就漏掉了。在如同当后面2个数字同为3的时候，因为一直相等，src同样+到空，3同样漏掉，所以无论哪种情况，都要把最后一个数字移到nums[dst]上
画图演示：
代码如下：
int removeDuplicates(int* nums, int numsSize){
int dst=0;
int src=1;
while(src<numsSize)
{
if(nums[src]==nums[src-1])
{
src++;
}
else
{
nums[dst]=nums[src-1];
dst++;
src++;
}
}
nums[dst]=nums[numsSize-1];
dst++;
return dst;
}
3、合并两个有序数组
链接直达：
题目：
思路：
法一：memmove + sort排序（冒泡、qsort等）
此法确实可以，不过当题目中明确指出要用时间复杂度O(N)的方法解决此问题的话，那么此法就行不通了，因为冒泡的时间复杂度为O(N^2)，而qsort的时间复杂度为O(N*logN)。均不是O(N)，所以得换。
法二：归并1.0
依次比较，每次把小的放到归并数组。此法需要开辟第三方数组a。其次，需要定义 i ，j ，dst 三个变量分别用来表示数组nums1，nums2，a的第一个下标，如果nums1[ i ]<nums[ j ]，则a[dst++]=nums1[ i++ ]，反之a[dst++]=nums2[ i++ ]，依次遍历下去，当其中一个走完了，就把剩下的全部放到a数组里头去，此法的最大问题就是需要额外开辟一个数组，以空间换时间，导致空间复杂度为O(N)，但是我们在基于此法的基础上可以进行升级，如下：
法三：归并2.0
此法是在法二的基础上进行升级，直接在nums1原数组上进行改动，思想和法二差不多。不过有个需要改变的地方，法二是正着遍历数组，但是此法则需要倒着来遍历数组。那么此时的 i 变量就是nums1数组第m-1个下标，j变量就是nums2数组第n-1个下标，dst变量就是nums1数组最后一个元素下标（m+n-1）。实现原理同法二，不做过多赘述。注意：如果nums2数组的下标 j 先结束，那么nums1剩下的数组刚好排在前面，不需要动，如果是nums1数组的下标 i 先结束，则需要把nums2数组剩余的值赋到nums1数组上去。
画图演示：
代码如下：
void merge(int* nums1, int nums1Size, int m, int* nums2, int nums2Size, int n){
int i=m-1;
int j=n-1;
int dst=m+n-1;
while(i>=0&&j>=0)
{
if(nums1[i]>nums2[j])
{
nums1[dst--]=nums1[i--];
}
else
{
nums1[dst--]=nums2[j--];
}
}
while(j>=0)
{
nums1[dst--]=nums2[j--];
}
}
到此这篇关于C语言经典顺序表真题演练讲解的文章就介绍到这了,更多相关C语言 顺序表内容请搜索我们以前的文章或继续浏览下面的相关文章希望大家以后多多支持我们！
相关推荐
-
详解C语言之顺序表
目录 一.思维导图 二.步骤 1.初始化 2.求表长 3.插入数据元素 4.删除数据元素 5.取出数据元素 按位查找 按位查找 所有代码 总结 一.思维导图 二.步骤 1.初始化 代码如下: void ListInit(SeqList *L) { L->size = 0; } 2.求表长 代码如下: int ListLength(SeqList L) { return L.size; } 3.插入数据元素 代码如下: int ListInsert(SeqList *L, int i, DataT
-
C语言的线性表之顺序表你了解吗
目录 线性表 —— 顺序表 (C语言) 1. 顺序表的储存结构 2. 顺序表的基本操作 2.1 顺序表的插入 2.2 顺序表的查找 2.3 顺序表的删除 总结 线性表 —— 顺序表 (C语言) 概念 线性表的顺序表示指的是用一组地址连续的存储单元依次存储线性表中的数据元素,这种表示也称做线性表的顺序储存结构或顺序映像.通常,称这种存储结构的线性表为顺序表 (Sequential List) .其特点是,逻辑上相邻的数据元素,其物理次序也是相邻的. 1. 顺序表的储存结构 #include <st
-
C语言 超详细顺序表的模拟实现实例建议收藏
目录 概念及结构 接口实现 1 顺序表的动态存储 2 顺序表初始化 3 顺序表的销毁 4 顺序表的尾插 5 顺序表的尾删 6 顺序表的头插 7 顺序表的头删 8 顺序表容量的检查与扩容 9 顺序表任意位置的插入 10 顺序表任意位置的删除 11 顺序表的打印 12 顺序表元素的查找 13 顺序表元素的修改 概念及结构 顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构,一般情况下采用数组存储.在数组 上完成数据的增删查改. 顺序表一般可以分为: 静态顺序表:使用定长数组存储元素,元素
-
C语言实现顺序表的基本操作指南(注释很详细)
目录 创建一个结构体用于存放顺序表相关数据 初始化顺序表 插入元素 先检查容量是否够用 删除元素 元素修改 查找元素 排序元素 元素反转 源码 SeqList.c test.c SeqList.h 总结 创建一个结构体用于存放顺序表相关数据 #define SEQTYPE int typedef struct SeqList { SEQTYPE* data; int size; //有效数据个数 int capacity; //容量 }SeqList; 初始化顺序表 void SeqListIn
-
新手向超详细的C语言实现动态顺序表
目录 一.各个函数接口的实现 1.1 不太好''李姐''的"容量检测函数" 1.2 在任意位置插入的函数"坑!" 1.3 在任意位置删除数据的函数 1.4 其余简单的接口函数 二.顺序表结构体声明与定义 三.头文件的调用 一.各个函数接口的实现 1.1 不太好''李姐''的"容量检测函数" 对顺序表进行插入数据时,需要判断顺序表的容量是否充足,增加数据的同时需要反复地检测容量,所以推荐直接将以上步骤封装成一个函数. 函数实现算法:若容量大小 ==
-
C语言数据结构深入探索顺序表
目录 1.线性表 2.顺序表 2.1概念及结构 2.2 接口实现 2.2.1初始化 2.2.2 检查容量 2.2.3 顺序表打印 2.2.4 顺序表尾插 2.2.5 顺序表尾删 2.2.6 顺序表头插 2.2.7 顺序表头删 2.2.8 顺序表在pos位置插入x 2.2.9 顺序表删除pos位置的值 2.2.10 尾插.尾删.头插.头删的改进 2.2.11 顺序表查找 2.2.12 顺序表销毁 2.3 数组相关面试题 2.4 顺序表的问题及思考 1.线性表 线性表(linear list)是n个
-
C语言线性表中顺序表超详细理解
目录 一.本章重点 二.线性表 三.顺序表 四.静态顺序表接口实现 4.1顺序表初始化 4.2顺序表打印 4.3顺序表尾插 4.4顺序表尾删 4.5顺序表头插 4.6顺序表头删 4.7顺序表任意位置插入 4.8顺序表任意位置删除 五.动态顺序表接口实现 5.1顺序表的初始化 5.2顺序表打印 5.3顺序表尾插 5.4顺序表尾删 5.5顺序表头插 5.6顺序表头删 5.7顺序表任意位置插入 5.8顺序表任意位置删除 六.在线0j练习 一.移除元素(力扣) 二.合并两个有序数组(力扣) 一.本章重点
-
C语言经典顺序表真题演练讲解
目录 1.移除元素 2.删除有序数组中的重复项 3.合并两个有序数组 1.移除元素 链接直达: https://leetcode-cn.com/problems/remove-element/ 题目: 思路: 法一:依次挪动数据进行覆盖 从第一个数据开始进行依次遍历,如同示例1,依次遍历数组,找到移除的元素2就把后面的数据往前挪动进行覆盖,如图所示: 此法有个缺陷,题目中明确指出使用空间复杂度O(1)的方法解决此问题,而此法的空间复杂度刚好为O(1),可以解决,不过考虑周全些,时间复杂度在情况最
-
利用C语言实现顺序表的实例操作
本文实例讲述了C语言实现顺序表(线性表)的方法.分享给大家供大家参考,具体如下: 一:顺序表代码实现 #ifndef _SEQ_LIST_H #define _SEQ_LIST_H #include <stdio.h> #include <stdlib.h> #include <assert.h> #include <string.h> #define ElemType float //以float类型测试算法通用性,而不是以惯用的int #define I
-
C语言实现顺序表的顺序查找和折半查找
本文实例为大家分享了C语言实现顺序表的顺序查找和折半查找的具体代码,供大家参考,具体内容如下 顺序查找: #include <iostream> using namespace std; int SeqSearch(int r[],int n,int k) { r[0]=k;//下标0用作哨兵存放要查询的数 int i=n; while(r[i]!=k)//不用判断下标i是否越界 { i--; } return i; } int main() { int n; cout<<&quo
-
C语言动态顺序表实例代码
目录 顺序表概念: 一.准备工作 二.顺序表的基本操作 1.顺序表的初始化函数 2.尾插函数(在尾部插入数据) 3.头插函数(在数组头部插入数据) 4.尾删函数 5.头删函数 6.在第pos的位置插入数据 7.删除第pos个位置的数据 8.修改第pos个位置的数据 9.查找函数. 10.销毁函数 11.打印函数 三.总代码: 顺序表概念: 顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构.一般情况下用数组存储.在数组上完成数据的增删查改. 代码解析: 一.准备工
-
C语言数据结构顺序表中的增删改(尾插尾删)教程示例详解
目录 初始化 尾插 格局打开 尾删 初始化 在初步认识顺序表这一结构后,我们就可以继续深入探究这是我之前在.h文件中创建的结构体 typedef int type; typedef struct list { type* a; int size; int capacity; }st; 在处理顺序表结构时我们会用到的一些接口,处理其中的关系,其实本质上就是函数,这里我用复杂英文对应出来方便形成记忆. void init(st *s); //插入 void pushback( st* p, type
-
C语言数据结构顺序表中的增删改(头插头删)教程示例详解
目录 头插操作 头删操作 小结 头插操作 继上一章内容(C语言数据结构顺序表中的增删改教程示例详解),继续讲讲顺序表的基础操作. 和尾插不一样,尾插出手阔绰直接的开空间,咱头插能开吗?好像没听说过哪个接口可以在数据前面开一片空间吧,那我们思路就只有一个了——挪数据.那应该从第一位开始挪吗?注意,这和 memcpy 函数机制是一样的,并不意味着后面数据一起挪动,也不会彼此独立,而是相互影响,挪动的数据会对后面数据进行覆盖. 那我们的逻辑就应该是从后往前挪,那我们就直接定一个下标,指向这段空间的最后
-
C语言数据结构顺序表的进阶讲解
目录 前言 一.顺序表的构造VS功能 1.顺序表的构造 2.接口实现(功能) 二.功能具体分析 1.初始化 2.销毁 3.检查size与capacity是否溢出 4.尾增功能(实现) 5.打印 三.实现具体功能代码页(SeqList.c) 四.总结 前言 在学习链表之前先掌握顺序表 什么是顺序表? 顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构一般情况下采用数组存储,在数组上完成数据的增删查改. 顺序表一般可分为: 1.静态顺序表:使用定长数组存储. 2.动态顺序表:使用动态开辟
-
C语言实现顺序表的全操作详解
目录 线性表 顺序表 顺序表接口实现 1.顺序表初始化 2.顺序表空间增容 3.顺序表打印 4.尾插数据 5.尾删数据 6.头插数据 7.头删数据 8.在pos下标处插入数据 9.删除pos下标处数据 10.数据查找 11.顺序表摧毁 线性表 线性表(linear list)是n个具有相同特性的数据元素的有限序列.线性表是一种在实际中广泛使用的数据结构,常见的线性表有:顺序表.链表.栈.队列.字符串等. 线性表在逻辑上是线性结构,也就是连续的一条直线.但在物理结构上并不一定是连续的,线性表在物理
-
C语言实现顺序表的基本操作的示例详解
目录 一.认识顺序表 1.线性表 2.顺序表的概念及结构 二.顺序表的基本操作(接口实现) 1.初始化顺序表 2.打印顺序表 3.尾插 4.尾删 5.扩容 6.头插 7.头删 8.任意位置插入 9.任意位置删除 10.查找某个数的位置 三.顺序表演示及代码(含源码) 1.演示效果 2.完整源代码 一.认识顺序表 1.线性表 线性表是n个具有相同特性的数据元素的有限序列,线性表是一种在实际中广泛使用的数据结构,常见的线性表有顺序表.链表.栈.队列.字符串……线性表在逻辑上是线性结构,也就是说是一条