一、概念
1.顺序存储
顺序存储结构,是指用一段地址连续的存储单元依次存储线性表的数据元素
2.存储方式
在编程语言中,用一维数组来实现顺序存储结构,在C语言中,把第一个数据元素存储到下标为0的位置中,把第 2 个数据元素存储到下标为 1 的位置中,以此类推。
3.长度和容量
数组的长度指的是数组当前有多少个元素,数组的容量值的是数字最大能存放多少个元素,数组越界就是因为超过了自己申请的数组的最大容量
4.数据结构定义
#define DataType int // (1)
struct SeqList {
DataType data[MAXN]; // (2)
int length; // (3)
};
(1)数组类型为DataType,定义为int;
(2)SeqList
定义的就是一个最多存放MAXN
个元素的数组,MAXN
代表数组容量;
(3)length代表数组长度,即当前的元素个数
二、常用接口实现
1.只读接口(帮助理解)
(1)索引
索引就是通过数组下标寻找数组元素的过程
DataType SeqListIndex(struct SeqList *sq, int i) {
return sq->data[i]; // (1)i的取值必须为非负整数
}
索引的算法时间为O(1)
(2)查找
通过数组元素寻找数组下标的过程
DataType SeqListFind(struct SeqList *sq, DataType dt) {
int i;
for(i = 0; i length; ++i) { // (1)遍历数组
if(sq->data[i] == dt) {
return i; // (2)找到了,返回下标
}
}
return -1; // (3)没找到,返回-1
}
(3)获取长度
获取 数组的长度 指的是查询当前有多少元素。可以直接用结构体的内部变量。C语言代码实现如下:
DataType SeqListGetLength(struct SeqList *sq) {
return sq->length;
}
2.可写接口
(1)插入
在数组的第K个元素前插入一个数V,因为数组是连续存储的,那么从K开始的所有元素都得往后移一位,给插入的元素V腾出一个空间,那么当K=0时,所有元素都得移动,所有最坏的时间复杂度为O(n).
C语言代码实现如下:
int SeqListInsert(struct SeqList *sq, int k, DataType v) {
int i;
if(sq->length == MAXN) {
return 0; // (1)当元素个数已经满的时候,说明无法再插入了
}
for(i = sq->length; i服务器托管网 > k; i--) {
sq->data[i] = sq->data[i-1]; // (2)从该数组的最后一位往后移动,一直到第K位也后移一位
}
sq->data[k] = v; // (3) 将第K位数变成V
sq->length ++; // (4) 数组长度加一
return 1; // (5) 返回1代表插入成功
}
(2)删除
将数组的第K个元素删除,因为数组存储是连续的,那么第K个元素删除,往后的元素势必要往前移动一位,当K=0时,所有元素都得移动,所以最坏时间复杂度为O(n)
C语言代码实现如下:
int SeqListDelete(struct SeqList *sq, int k) {
int i;
if(sq->length == 0) {
return 0; // (1) 返回0代表失败
}
for(i = k; i length - 1; ++i) {
sq->data[i] = sq->data[i+1]; // (2) 从前往后覆盖
}
sq->length --; // (3) 数组长度减一
return 1; // (4) 返回1代表删除成功
}
三、优缺点
1.优点
(1)无须为表示表中元素逻辑关系而增加额外的存储空间
(2)随机存取元素时可以达到O(1),效率高
2.缺点
(1)插入和删除时需要移动大量元素
(2)必须一开始就确定存储空间的容量
四、数组相关算法
1、线性枚举
(1)问题描述
给定一个长度为 n(1≤n≤105) 的整型数组,求所有数组元素中的其中的最小值
(2)算法描述
遍历数组,进行条件判断,条件满足则执行逻辑。这里的条件就是 枚举到的数 是否小于 当前最小值,执行逻辑为 将 当前枚举到的数 赋值给 当前最小值;
代码示例如下:
int findMin(int* nums, int numsSize){
int min = 100000;
for(int i = 0; i
2、前缀和差分
(1)问题描述
给定一个 n(n≤105) 个元素的整型数组 ai,再给出 m(m≤105)次询问,每次询问是一个区间 [l,r],求 h(l,r)=∑rk=lak
(2)算法描述
第一个枚举,利用一个数组sum,存储前i个元素的和
第二个枚举,读入m 组数据 l,r,对每组数据,通过 O(1)获取答案,即 sumr-suml-1
代码示例如下:
int sum[maxn];
int* prefixSum(int* nums, int numsSize, int m, int *l, int *r){
int i;
int *ret;
for(i = 0; i
3、双指针
(1)问题描述
给定一个长度为 n(1≤n≤107)的字符串 s,求一个最长的满足所有字符不重复的子串。
(2)算法描述
如上文所述,这种利用问题特性,通过两个指针,不断调整区间,从而求出问题最优解的算法就叫 “尺取法”,由于利用的是两个指针,所以又叫 “双指针” 算法。
这里 “尺” 的含义,主要还是因为这类问题,最终要求解的都是连续的序列(子串),就好比一把尺子一样,故而得名。
算法描述如下:
(1)初始化 , ,代表一开始 “尺子” 的长度为 0;
(2)增加 “尺子” 的长度,即 ;
(3)判断当前这把 “尺子” 是否满足题目给出的条件:
(3.a)如果不满足,则减小 “尺子” 长度,即 ,回到 (3);
(3.b)如果满足,记录最优解,回到 (2);
核心算法就是:满足条件,j++,反之,i++
代码示例如下:
int getmaxlen(int n, char *str, int& l, int& r) {
int ans = 0, i = 0, j = -1, len; // (1)初始化
memset(h, 0, sizeof(h)); // (2)h代表的是一个哈希表,memset是初始化哈希
哈希表记录的是当前枚举的区间S[i,j]中每个字符的个数
while (j++ 1) { // (5)当h[str[j]] > 1时,说明出现了重复字符串str[j]
左端点i开始右移,直到没有重复字符为止
--h[ str[i] ];
++i;
}
len = j - i + 1;
if(len > ans) // (6)len = j - i + 1;记录当前最优解的长度,更新
ans = len, l = i, r = j;
}
return ans;
}
4、二分枚举
(1)问题描述
给定一个 n(n≤106)个元素的有序整型数组和一个 target值,求在 O(log2n) 的时间内找到值为 target 的整型的数组下标,不存在则返回 -1。
(2)算法描述
(a)初始情况下,令右端点r=n-1;左端点l=0;
(b)生成一个中间值mid = (r+l)/2;
(b.1)目标等于mid,返回mid;
(b.2)目标元素大于mid, l=mid+1;
(b.3)目标元素小于mid, r=mid-1;
(c)当l>r的时候,则说明没有找到目标值,返回-1,否则,回到b,继续迭代
代码示例如下:
int search(int *nums, int numsSize, int target) {
int l = 0, r = numsSize - 1; // (1)初始化l,r
while(l服务器托管网 > 1; // (3)中间点
if(nums[mid] == target) {
return mid; // (4)找到目标,返回下标mid
}else if(target > nums[mid]) {
l = mid + 1; // (5)左端点移动到 mid+1
}else if(target
5、三分枚举
三分枚举 类似 二分枚举 的思想,也是将区间一下子砍掉一块基本完全不可能的块,从而减小算法的时间复杂度。只不过 二分枚举 解决的是 单调性 问题。而 三分枚举 解决的是 极值问题。
6、插入排序
(1)问题描述
给定一个n个元素的数组,数组下标从0开始,采用插入排序将数组升序排列
(2)算法描述
(1) 循环迭代变量 ;
(2) 每次迭代,令 ,,循环执行比较 和 ,如果产生 则执行 。然后执行 ,继续执行 (2);否则,跳出循环,回到 (1)。
示例代码如下:
void InsertSort(int n, int *a) {
int i, j;
for(i = 1; i = 0; j--)
{ // (2)逆序的枚举所有已经排好序的数
if(x
7、选择排序
(1)问题描述
给定 个元素的数组,数组下标从 开始,采用「 选择排序 」将数组按照 「升序」排列
(2)示例代码
void Swap(int *a, int *b) {
int tmp = *a;
*a = *b;
*b = tmp;
}
void SelectionSort(int n, int *a) {
int i, j;
for(i = 0; i
8、冒泡排序
void MaoPao(int n,int *a)
{
for(int i=0;i
时间复杂度为O(n2)
服务器托管,北京服务器托管,服务器租用 http://www.fwqtg.net
机房租用,北京机房租用,IDC机房托管, http://www.fwqtg.net
相关推荐: #yyds干货盘点# LeetCode程序员面试金典:根据身高重建队列
1.简述: 假设有打乱顺序的一群人站成一个队列,数组表示队列中一些人的属性(不一定按顺序)。每个表示第个人的身高为,前面正好有个身高大于或等于的人。peoplepeople[i] = [hi, ki]ihikihi 请你重新构造并返回输入数组所表示的队列。返回…