学会基础思想,针对不用情况做变型和调整
//#include<cstdio>
//#include<iostream>
//#include<algorithm>
//#include<cstring>
//#define Maxsize 11
//using namespace std;
1.设计一个算法删除线性表x到y的所有元素
算法分析:
①有序的话,先定位再删除;
②无序的话,双指针对原数组更新(类似于练习1的第4个类型题)
注意: 无序的写法,是这一类问题的模板写法,对有序也有同样适用
// 线性表为递增排序的条件下
void fun_1_1(List &L,int x,int y)
{
//先判断x和y是否合法,以及表是否为空
if(x > y || L.len < 0) return;
//遍历线性表,分别取出x,y元素对应左右区间边界的元素下标分别交给m,n做记录
int m, n;
for(int i = 0;L.data[i] <= x || L.data[i] <= y;i ++)
if(L.data[i] <= x) m = i;
else if(L.data[i] <= y) n = i;
//因为线性表递增有序,所以直接删除m到n的符合题意区间元素(这里写得简短,但是逻辑很绕仔细品)
for(i = n + 1;i < L.len;i ++)
L.data[i - (n - m + 1)] = L.data[i];
//更新线性表
L.len -= n - m + 1;
}
// 线性表为无序的条件下
void fun_1_1(List &L,int x,int y)
{
//先判断x和y的参数是否合法
if(x < y) return;
//双指针算法:i为遍历原线性表,j为更新线性表
for(int i = 0,j = 0;i < L.len;i ++)
if(L.data[i] < x && L.data[i] > y)
{
L.data[j] = L.data[i];
j ++;
}
//更新线性表
L.len = j;
}
2.设计一个算法将小于0的整数放在前部分,大于等于0的整数放在后部分
算法分析:双指针算法,i从前往后,j从后往前,按条件交换元素直到相遇为止
void fun_2(List &L){
int i = 0,j = L.len - 1;
while(i < j)
{
while(L.data[i] < 0) i ++;
while(L.data[j] >= 0) j --;
if(i < j)//防止,最后完成以后,ij越界交换
{
int t = L.data[i];
L.data[i] = L.data[j];
L.data[j] = t;
}
}
}
3.设计一个算法删除重复元素
算法分析:
①有序情况,直接用fun_1_2的模板写法,条件改改,处理一下细节即可
②无序情况,先用数组模拟哈希表做记录,然后再用fun_1_2的模板基础上改写一下即可
// 线性表为有序的条件下去重
void fun_3(List L)
{
//判断表是否为空or不需要去重
if(L.len == 0 || L.len == 1) return;
//双指针算法:i为遍历原线性表,j为更新线性表
//注意:这里最关键的是要先对j++再更新原数组,不然会出现元素丢失
for(int i = 0,j = 0;i < L.len;i ++)
if(L.data[i] != L.data[j])
{
j ++;
L.data[j] = L.data[i];
}
//更新线性表
L.len = j;
}
// 线性表为无序的条件下去重
//放在函数外面做全局变量,系统会自动对数组初始化为全0,哈希表来用下标做元素,空间做记录重复次数
int hash[100010];
//注意:当然你也可以吧hash定义在函数里面,但是要写memset(hash,sizeof(hash),0)来初始化为0,因为数组在函数里面定义不会自动初始化为0
void fun_3(List L)
{
//判断表是否为空or不需要去重
if(L.len == 1 || L.len == 0) return;
//开一个非常大的数组用下标来做元素值,存在的元素存储空间放1
for(int i = 0;i < L.len;i ++) hash[ L.data[i] ] = 1;
//
for(int i = 0,j = 0;i < L.len;i ++)
if(hash[L.data[i]])
{
//当元素第一次出现的时候,就把哈希表置0,这样就达到了更新原数组去重
hash[L.data[i]] = 0;
L.data[j] = L.data[i];
j ++;
}
//更新线性表
L.len = j;
}
返回目录:
https://www.acwing.com/file_system/file/content/whole/index/content/5976074/