介绍
顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构，一般情况下采用数组存储。在数组上完成数据的增删查改。
// 顺序表的静态存储
#define N 100
typedef int SLDataType;
typedef struct SeqList
{
SLDataType array[N]; // 定长数组
size_t size; // 有效数据的个数
}SeqList;
// 顺序表的动态存储
typedef struct SeqList
{
SLDataType* array; // 指向动态开辟的数组
size_t size ; // 有效数据个数
size_t capicity ; // 容量空间的大小
}SeqList;
特点
- 可动态增长的数组
- 数据在数组中必须是连续的
缺点
- 中间或者头部插入删除很慢，需要挪数据。时间复杂度O（N）
- 空间不够时，会进行增容消耗一定空间
优点
-
随机访问
-
缓存利用率较高
OJ
1.移除元素
给你一个数组 nums 和一个值 val，你需要 原地 移除所有数值等于 val 的元素。元素的顺序可能发生改变。然后返回 nums 中与 val 不同的元素的数量。
假设 nums 中不等于 val 的元素数量为 k，要通过此题，您需要执行以下操作：
- 更改
nums数组，使nums的前k个元素包含不等于val的元素。nums的其余元素和nums的大小并不重要。 - 返回
k。
算法思路：依次遍历数组中每一个元素，初始cur指向数组下标0的位置，每次出现与val不等的元素，把它放到cur所指的位置，然后cur指向下一个位置，直到最后i变量把整个数组遍历完，用变量cur记录了最终不等于val的个数。
int removeElement(int* nums, int numsSize, int val) {
int cur = 0;//记录不等于val的个数
for(int i = 0;i<numsSize;i++)
{
if(nums[i]!=val)
{
nums[cur]=nums[i];
cur++;
}
}
return cur;
}
2.删除排序数组中的重复项
给你一个 非严格递增排列 的数组 nums ，请你 原地 删除重复出现的元素，使每个元素 只出现一次 ，返回删除后数组的新长度。元素的 相对顺序 应该保持 一致 。然后返回 nums 中唯一元素的个数。
考虑 nums 的唯一元素的数量为 k ，你需要做以下事情确保你的题解可以被通过：
-
更改数组
nums，使nums的前k个元素包含唯一元素，并按照它们最初在nums中出现的顺序排列。nums的其余元素与nums的大小不重要。 -
返回
k。
算法思路：利用两个紧挨着的变量start,end一前一后哦，来进行数组遍历，如果start所指向的值与end指向的值不同时（start所指元素就是该元素最后一次重复出现的位置），把start所指的元素赋值给cur所指的位置，cur后移一位，start和end也后移一位，以此类推，直到end出界，数组循环遍历结束，此时start指向数组中最后一个元素位置（注意：start所指元素是该元素最后一次重复出现的位置），要把start最后所指元素赋值给cur所指位置。
int removeDuplicates(int* nums, int numsSize) {
int cur = 0;
int start = 0,end =1;
if(numsSize==0)
return 0;
while(end<numsSize)
{
if(nums[start]!=nums[end])
{
nums[cur]=nums[start];
cur++;
}
start++;
end++;
}
//注意最后start还是一个未录入的元素,end出界
nums[cur] = nums[start];
cur++;
start++;
return cur;
}
3.数组形式的整数加法
整数的 数组形式 num 是按照从左到右的顺序表示其数字的数组。
- 例如，对于
num = 1321，数组形式是[1,3,2,1]。
给定 num ，整数的 数组形式 ，和整数 k ，返回 整数 num + k 的 数组形式 。
算法思路：主要还是通过整数加法中每一位相加总的运算次数，对num数组从后往前遍历的每一位与k值的每一位相加，得出的最终结果长度不会超过[max(num长度，k值长度)+1]，通过计算每一位相加结果是否大于9（向下一位进位），每一位结果记录到resArr结果数组中，最后逆置一下得到最终结果。
/**
* Note: The returned array must be malloced, assume caller calls free().
*/
int* addToArrayForm(int* num, int numSize, int k, int* returnSize) {
//找出两数最长的位数，(运算次数)
int kSize = 0,kNum = k;
while(kNum)
{
kNum/=10;
kSize++;
}
int len = kSize>numSize?kSize:numSize;
//最终求和结果最长是len+1，如果两个数长度相等也可能是len+1
int* resArr = (int*)malloc(sizeof(int)*(len+1));
int resi = 0;//结果数组下标
int res = 0;//每一位相加结果
int i = numSize-1;
int nextNum = 0;//进位
while(len--)
{
//注意：numSize长度<被加数k长度，i可能<0越界
int cur = 0;
if(i>=0)
{
cur = num[i];
i--;
}
//记录每一位求和值
res = cur+ k%10+nextNum;
//i--;
k/=10;
if(res>9)
{
res-=10;
nextNum = 1;
}
else
{
nextNum = 0;
}
resArr[resi]=res;
resi++;
}
if(nextNum==1)//可能出现num和k长度相等
{
resArr[resi]=1;
resi++;
}
//逆置结果数组
int left = 0,right = resi-1;
while(left<right)
{
int tmp = resArr[left];
resArr[left] = resArr[right];
resArr[right] = tmp;
left++;
right--;
}
*returnSize = resi;
return resArr;
}
给你一个整数数组 nums，其中恰好有两个元素只出现一次，其余所有元素均出现两次。 找出只出现一次的那两个元素。你可以按 任意顺序 返回答案。
你必须设计并实现线性时间复杂度的算法且仅使用常量额外空间来解决此问题。
示例 1：
输入：nums = [1,2,1,3,2,5]
输出：[3,5]
解释：[5, 3] 也是有效的答案。
示例 2：
输入：nums = [-1,0]
输出：[-1,0]
示例 3：
输入：nums = [0,1]
输出：[1,0]
算法思路：以[1, 2, 1, 3, 2, 5]为例，全部异或一遍的结果是3^5，得到ret为6；6&-6得到ret=2，意思是6中低位第一个出现的1，令ret为2；然后进行分组异或，
/**
* Note: The returned array must be malloced, assume caller calls free().
*/
int* singleNumber(int* nums, int numsSize, int* returnSize) {
long ret = 0;
//计算出现一次的两个元素异或的结果
for(int i = 0;i<numsSize;i++)
{
ret ^= nums[i];
}
// 找出ret第m位为1的位置
// int m = 0;
// while(m<64)
// {
// if(ret & (1<<m))
// break;
// else
// ++m;
// }
ret = ret&(-ret);
//分组
//把数组分为第m位为1的是一组
//第m位不是1的为一组
int x1 = 0, x2 = 0;
for(int i = 0;i<numsSize;i++)
{
if(nums[i] & ret)
x1 ^= nums[i];
else
x2 ^= nums[i];
}
int* retArr = (int*)malloc(sizeof(int)*2);
retArr[0] = x1;
retArr[1] = x2;
*returnSize = 2;
return retArr;
}
