题目描述
解题思路
方法一：利用 map，每出现一个新的朋友证号就会在 map 中增加一个元素。最后遍历 map 输出即可得到有序结果序列。和方法二相比，主要优势在于节约了内存空间。
方法二：利用 hash 数组，记录每个数是否是朋友证号，如是设为 true，最后按顺序遍历数组，输出值为 true 的序号。
也许陌生的知识点
map<int, int> m;- 用于映射，键和值可以是任意类型
- 直接使用
m[<键>] = <值>即可向map中添加一组键值对 - 需要的头文件：map
for(auto it = m.begin(); it != m.end(); it++){}- 可用于遍历 map/vector/set 等容器，
auto实现自动匹配对应迭代器类型 - 如果不用
auto it = m.begin()则要写成std::map<char, int>::iterator it = m.begin() map<char,int>在其他情况下可替换成对应元素的类型如vector<int>- 所需头文件： map / set / vector
- 可用于遍历 map/vector/set 等容器，
it->first和it->secondit->first为 map 中对应元素的关键字it->second为 map 中对应关键字的值- 所需头文件： map
代码示例：
方法一：利用 map
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
using namespace std;
int main(){
int n, cnt = 0;
string temp;
map<int, int> m;
scanf("%d", &n);
for(int i = 0; i < n; i++){
int sum = 0;
cin >> temp;
for(int j = 0; j < temp.length(); j++) sum = sum + (int)(temp[j] - '0');
m[sum]++;
}
printf("%d\n", m.size());
for(auto it = m.begin(); it != m.end(); it++, cnt++){
if(cnt != 0) printf(" ");
printf("%d", it->first);
}
return 0;
}方法二：利用 hash 数组
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
int main() {
int n, num = 0;
bool h[50] = {false};
scanf("%d", &n);
for(int i = 0, temp, sum; i < n; i++, sum = 0){
scanf("%d", &temp);
while(temp!=0){
sum = sum + temp % 10;
temp /= 10;
}
if(h[sum] == false){
num++;
h[sum] = true;
}
}
printf("%d\n", num);
int flag = 0;
for(int i = 1; i < 50; i++){
if(h[i]) {
if(flag != 0) printf(" ");
printf("%d", i);
flag++;
}
}
return 0;
}