当前位置：首页 > article >正文

sort排序计数排序 map set C++ 蓝桥杯

article 2025/2/5 15:17:03

单词排序

#include<iostream>
#include<set>
using namespace std;
int main() {
	set<string>s;
	string t;
	while (cin >> t) {
		s.insert(t);
	}
	for (auto i : s) cout << i << endl;
	return 0;
}

单词排序思路：set自动去重排序

set：

// 创建集合：set<int>s; 关键字<集合元素类型>集合名

// 向集合插入元素：s.insert(x) 向集合中插入x，集合自动去重排序

// 增强for循环输出：for(auto i:s) auto自动从头到尾访问集合s里的每一个元素，cout<<i<<" "输出每一个元素

// while(cin>>x) 当停止输入时，while会结束循环。在自己测评时，需要换行，按ctrl+Z表示停止输入。这个是在不知道要输入多少个变量时可以用。

#include<iostream>
#include<algorithm>
using namespace std;
string a[110];
int main() {
	string s;
	int i = 1;
	while (cin >> s) {
		a[i++] = s;
	}
	sort(a + 1, a + i);
	int r = 1, l = 1;
	while (l != i ) {
		while (a[l] == a[r]) {
			r++;
		}
		cout << a[l]<<endl;
		l = r;
		r++;
	}
	return 0;
}

单词排序思路：string数组，sort排序，双指针去重

详细思路：开一个字符串数组，输入字符串到数组里，对数组进行排序（通过sort)，输出的时候通过双指针，l在左，r在右，当没有遍历完所有字符串时，用循环过滤a[l]==a[r]，a[l]与a[r]相等，就让r++，直到不等，那就输出a[l]，l=r，r++。这样就达到去重了。

出现次数超过一半的数

#include<iostream>
#include<cmath>
using namespace std;
int a[110];
int main() {
	int n; cin >> n;
	for (int i = 1; i <= n; i++) {
		int x; cin >> x;
		a[x + 50]++;
	}
	for (int i = 0; i <= 100; i++) {
		if (a[i] >= ceil(n / 2.0)) {
			cout << i-50;
			return 0;
		}
	}
	cout << "no";
	return 0;
}

出现次数超过一半的数——解决思路：

方法一

计数排序解决：

思路来源：要算出现次数超过一半的数，所以想到计数排序，去统计每个数出现的次数。

计数排序：通过下标 i 来记录要统计的数，而下标对应的 a[i] 数值是该下标这个数出现的次数。所以由这个本质可知，计数数组的大小开为待统计数的最大值+10（+10是为了防止数据溢出，出现访问越界的问题）。

所以本题思路：先用计数排序数组去统计每个数出现的次数（因为这里给的数是-50~50，所以统计的时候需要原数加上50之后再计数，因为数组下标没有负数，对应输出满足超过ceil(n/2.0)总数的一半的数时，需要让这个数减去50），再通过循环遍历所有可能的下标，判断数组值是否大于总个数的一半即ceil(n/2.0)，这里需要向上取整，因为样例里表明3个数的一半是2，所以这里得向上取整。

#include<iostream>
#include<map>
#include<cmath>
using namespace std;
int main() {
	map<int, int>m;
	int n; cin >> n;
	int c = n;
	//cout << ceil(n / 2) << endl;   注意向上取整有意义需要数是浮点型
	while (c--) {
		int x; cin >> x;
		m[x]++;
	}
	for (map<int, int>::iterator it = m.begin(); it != m.end(); it++) {
		//cout << it->first << " " << it->second << endl;
		if (it->second >= ceil(n / 2.0)) {
			cout << it->first;
			return 0;
		}
	}
	cout << "no";
	return 0;
}

出现次数超过一半的数：

方法二：

stl容器map解决：利用map相当于再计数排序上优化了，解决下标不能为负数的问题。

须知知识——map知识点：

具体一个map容器创建：map<int,int>m——关键字<键的类型，值的类型>map名字

[] ：中括号插入键，对应值直接m[x]=a；创建键为x，对应值为a的键值对。直接创建时，未赋值时，值为0。如果键不存在，那么[]，就是创建这个键，若存在，那么[] ，就是访问这个键的值。

迭代器map<int,int>::iterator it：map<int,int>这个类型下的迭代器it

迭代器关键字：iterator（可以理解为指向一个地址）

// it=m.begin();it!=m.end();it++

m.begin()：m这个容器的首元素地址

m.end()：m这个容器为尾元素地址的后一位

用it迭代器访问map键值对：需要用箭头，或者*