数组例题——使用数组下标查询结果

先来看一个问题：输入整数 \(y\) 和 \(m\)，输出公元 \(y\) 年 \(m\) 月的天数。

首先想到的是使用多分支结构来进行分类讨论：

#include<iostream>
using namespace std;
int main()
{
	int y,m;
	cin>>y>>m;
	if(m==1 || m==3 || m==5 || m==7 || m==8 || m==10 || m==12){  //大月 
		cout<<31<<endl;
	}else if(m==4 || m==6 || m==9 || m==11){  //小月 
		cout<<30<<endl;
	}else{  //2月 
		if(y%4==0 && y%100!=0 || y%400==0){  //闰年 
			cout<<29<<endl;
		}else{  //平年 
			cout<<28<<endl;
		}
	}
    return 0;
}

其实还可以将一年里\(12\)个月的天数存放到一个数组a里：\(1\)月的天数存放到\(a[1]\)，\(2\)月的天数存放到\(a[2]\)，……，\(12\)月的天数存放到\(a[12]\)（抽象概括就是 \(i\)月的天数存放在数组 \(a[i]\)元素中），这样月份的序号和存放该月天数的数组元素下标一一对应。那么\(m\)月的天数就在\(a[m]\)中，直接输出\(a[m]\)即可。需要注意的是，\(2\)月的天数要分闰年、平年处理。

#include<iostream>
using namespace std;
int main()
{
	int y,m;
	cin>>y>>m;
	//定义数组并为所有元素赋初值
	//a[0]不用；a[2]值为28，默认是平年 
	int a[13] = {0,31,28,31,30,31,30,31,31,30,31,30,31};
	//如果是闰年，修改2月天数 
	if(y%4==0 && y%100!=0 || y%400==0){
		a[2]++;
	}
	//输出m月天数（就存放在a[m]中） 
	cout<<a[m]<<endl; 
    return 0;
}

将每月天数巧妙地存放到数组中，月份的序号和存放该月天数的数组元素下标一一对应，这样通过下标直接就能查到指定月份的天数。这种根据问题构造与结果相关的数组，通过下标查询结果的方法，大家注意体会。类似于数学中的映射、现实生活中的根据索引查表。

再来看一个例题，输入\(n\)个\(0～10000\)范围内的整数，找到出现次数最多的整数，输出它出现的次数。

现实生活中，可以在一张纸上写下所有的整数，然后用“画正字”的方法来统计每个整数出现的次数，其实就是为每个整数设计了一个计数器来记录该整数出现的次数。那么在程序中可以开一个数组，数组的每个元素都是计数器，来记录每个整数出现的次数。

这里输入的整数集中在一个区间\(0～10000\)，那我们开一个数组a[10001]用来存放\(0～10000\)每个整数出现的次数，a[0]存放的是0出现的次数，a[1]存放的是1出现的次数，……，a[10000]存放的是10000出现的次数（抽象概括就是数组 \(a[i]\)元素存放的是整数 \(i\) 出现的次数），这样整数和存放整数出现次数的数组元素下标一一对应。那么输入一个整数k，意味着k出现了一次，只需要a[k]++即可更新它出现的次数。所有数据输入完毕后，数组中存放了这个范围内的每个整数出现的次数，只需要计算数组所有元素的最大值即可。

#include<iostream>
using namespace std;
//开全局int数组，数组的每个元素初始值为0
//正好符合开始时，每个数出现的次数为0 
int a[10001];
int main()
{
	int n,k;
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>k;
		a[k]++;		//k出现次数+1 
	}
	
	//打擂求数组所有元素最大值 
	int max = 0;
	for(int i=0;i<=10000;i++){
		if(a[i]>max) max = a[i];
	}
	cout<<max<<endl;
    return 0;
}

进一步，还是输入\(n\)个\(0～10000\)范围内的整数，如何将这些整数去重后按照从小到大的顺序输出呢？还是采用上面的策略，所有数据输入完毕后，数组中存放了这个范围内的每个整数出现的次数，我们只需要从小到大依次考察\(0～10000\)范围内的每个整数，只要出现过，输出即可，这样就实现了去重+排序的效果。

#include<iostream>
using namespace std;
//开全局int数组，数组的每个元素初始值为0
//正好符合开始时，每个数出现的次数为0 
int a[10001];
int main()
{
	int n,k;
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>k;
		a[k]++;		//k出现次数+1 
	}
	
	//从小到大依次考察每个整数 
	for(int i=0;i<=10000;i++){
		//i出现过，输出i 
		if(a[i]>0) cout<<i<<" ";
	}
    return 0;
}

那如果输入的整数范围是\(-10000～10000\)，该如何处理呢？

如果还是 cin>>k; a[k]++; 很显然，输入负数的时候，下标k是负数，这不符合语法，会出现运行时错误。那怎么避免下标出现负数呢？开一个数组a[20001]用来存放\(-10000～10000\)每个整数出现的次数，a[0]存放的是-10000出现的次数，a[1]存放的是-9999出现的次数，……，a[10000]存放的是0出现的次数，a[10001]存放的是1出现的次数，……，a[20000]存放的是10000出现的次数（抽象概括就是数组 \(a[i+10000]\)元素存放的是整数 \(i\) 出现的次数），这样整数和存放整数出现次数的数组元素下标仍然一一对应。那么输入一个整数k，意味着k出现了一次，只需要a[k+10000]++即可更新它出现的次数。

#include<iostream>
using namespace std;
const int N = 10000;
//开全局int数组，数组的每个元素初始值为0
//正好符合开始时，每个数出现的次数为0 
int a[2*N+1];
int main()
{
    int n,k;
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>k;
        a[k+N]++;        //k出现次数+1 
    }
    
    //打擂求数组所有元素最大值 
    int max = 0;
    for(int i=-N;i<=N;i++){
        if(a[i+N]>max) max = a[i];
    }
    cout<<max<<endl;
    return 0;
}

#include<iostream>
using namespace std;
const int N = 10000; 
//开全局int数组，数组的每个元素初始值为0
//正好符合开始时，每个数出现的次数为0 
int a[2*N+1];
int main()
{
	int n,k;
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>k;
		a[k+N]++;		//k出现次数+1 
	}
	
	//从小到大依次考察每个整数 
	for(int i=-N;i<=N;i++){
		//i出现过，输出i 
		if(a[i+N]>0) cout<<i<<" ";
	}
    return 0;
}