|
# 数组 ## 输入输出 输入一个数字n，输入n个数字（1<=n<=10^6） ```c++ int n; cin>>n; int a[1000050]={}; for(int i=0;i<n;i++){ cin>>a[i]; } for(int i=1;i<=n;i++){ cin>>a[i]; } for(int i=0;i<n;i++){ cout<<a[i]<<" "; } for(int i=1;i<=n;i++){ cout<<a[i]<<" "; } int b[10]; cout<<b;//输出首元素的首地址（十六进制的数据） cout<<&b[0]<<" "<<&b[1];//差4 地址操作：+ 代表下一个位置 for(int i=0;i<n;i++){ cout<<*(b+i); } ``` 数组创建时[长度] 数组使用时[下标] 数组的下标是从0开始的 # 练习题 ## 2034 输入没有明确结束限制 ```c++ int main(){ int a[105]={}; int i=0; while(cin>>a[i]){ i++; } for(int j=i-1;j>=0;j--){ cout<<a[j]<<" "; } return 0; } ``` ## 2038 ```c++ int main(){ int n; long long a[1050]={}; cin>>n; int maxid=0; for(int i=1;i<=n;i++){ cin>>a[i]; if(a[i]>a[maxid]) maxid=i; } cout<<maxid; return 0; } ``` ## 1107 ```c++ #include <iostream> using namespace std; int main(){ int l[10050]={},m,s,e,n; cin>>n>>m; fill(l,l+n+1,1); while(m--){ cin>>s>>e; fill(l+s,l+e+1,0); } int ans=0; for(int i=0;i<=n;i++){ if(l[i]==1) ans++; } cout<<ans; return 0; } ``` ## 一到四章 尽快做完 # 数组的其他用法 ## 桶排序（空间换时间） 把下标设置成数据，空间记录数据出现的次数 输入一个数字n(0~100)，输入n个数字(0~100000) 将数字按从小到大排序并去重 输入： 10 6 2 4 7 4 5 3 1 6 7 输出： 1 2 3 4 5 6 7 ```c++ int n; int a[100050]={},aa; cin>>n; for(int i=0;i<n;i++){ cin>>aa; a[aa]++; } //排序并去重 for(int i=0;i<100050;i++){ if(a[i]>0) cout<<i<<" "; } //排序不去重 for(int i=0;i<100050;i++){ int j=a[i]; while(j--) cout<<i<<" "; } ``` 桶排序的限制： 数据范围不能太大(超内存) 不能用下标（没法存） 桶排序的特殊情况： 有负数有正数排序（-100～100） ```c++ int n; int a[250]={},aa; cin>>n; for(int i=0;i<n;i++){ cin>>aa; a[aa+100]++; } for(int i=0;i<250;i++){ if(a[i]>0) cout<<i-100<<" "; } ``` 有字符 ```c++ int n; int a[150]={}; char aa; cin>>n; for(int i=0;i<n;i++){ cin>>aa; a[aa]++; } for(int i=0;i<150;i++){ if(a[i]>0) cout<<char(i)<<" "; } ``` ## 冒泡排序 反复：从头到尾依次比较相邻的两个元素，看是否需要交换 ```c++ int a[10]={}; int n; cin>>n; for(int i=0;i<n;i++){ cin>>a[i]; } for(int i=0;i<n-1;i++){ for(int j=0;j<n-1-i;j++){ if(a[j]>a[j+1]) { swap(a[j],a[j+1]); } } } for(int i=0;i<n;i++){ cout<<a[i]<<" "; } ``` ## 选择排序 反复：每轮从未排序的数组里找到最小（大）的值，与第一个值进行交换 ```c++ int a[10]={}; int n; cin>>n; for(int i=0;i<n;i++){ cin>>a[i]; } for(int i=0;i<n-1;i++){ int k=i; for(int j=i;j<n;j++){ if(a[j]<a[k]) { k=j; } } swap(a[i],a[k]); } for(int i=0;i<n;i++){ cout<<a[i]<<" "; } ``` ## 插入排序 每轮从未排序的数组里取头数字，放到有序数组从后往前依次比较 ## 作业（尽快） 一到四章 ## 作业 1、小鱼比可爱： https://www.luogu.com.cn/problem/P1428 2、不吉利日期： https://blog.csdn.net/bjxqmy/article/details/97904536 3、三天打渔两天晒网： 输入两组年月日 1998 12 30 2024 1 1 输出 设：1998年12月30日是打渔第一天，2024年1月1日是在打渔还是晒网 4、车厢重组： ybt.ssoier.cn:8088/problem_show.php?pid=1310 (责任编辑：admin) |