桶

• 1. 桶结构
• 2. 桶排序

1. 桶结构

将桶单独拿出来讲，是为了讲后面的离散化

• 当数组中每个元素的大小范围给定时并且不超过空间限制时，用该数组的下标或下标+偏移量映射为该值的大小，数组的值表示该数字出现的次数的数据结构
• 优点：有效提高数据的访问效率和处理速度
• 缺点：必须知道每个元素的大小范围并且能够映射到$[0,N]$才可以使用

例题：1186：出现次数超过一半的数 信息学奥赛一本通（C++版）

• 桶做法

#include<bits/stdc++.h>
#define x first
#define y second

using namespace std;

typedef long long ll;
typedef pair<int,int> PII;

// 解题思路: 

const int N=1e2+10; // (-50,50),(0,100),[1,99]
int a[N]; // 桶
// 什么时候用桶→每个数据的范围给定
// 下标代表这个数字,或者这个数字的映射值,数组的值代表出现的次数

// temp:临时变量,nm n表示行,m表示列
// ans:answer, res:result, cnt:count

// 排序:冒泡/交换/选择 O(n²), 快排/希尔排序/归并排序O(nlogn)/sort, 桶排序O(n)

int main() {
	int n;
	cin>>n; // 5: 2 4 2 5 9
	for(int i=1;i<=n;i++) {
		int temp;
		cin>>temp;
		a[temp+50]++; // a[2]++,a[2]=1,a[4]=1,a[2]=2
	}
	// 遍历所有可能的大小,其实就遍历了所有的数字
	// 如果根本没出现过,a[i]=0
	bool flag=false;
	for(int i=1;i<=99;i++) {
		// a[i]代表出现的次数
		if(a[i]>n/2) {
			flag=true;
			cout<<i-50;
		} 
	}
	if(flag==false) cout<<"no";
	return 0;
}

• map做法

• $map$是$C++$ STL库中自带的一种数据结构，可以理解为$Python$中的$dict$字典数据结构，map中有两个关键字，一个是键(索引)，一个是键值，它是一个二元组，和本题不谋而合，让第一个关键字存储这个值的大小，第二关键字存储出现的次数即可，而且不用考虑从$[-49,49]$映射到$[1,99]$

#include<bits/stdc++.h>
#define x first
#define y second

using namespace std;

typedef long long ll;
typedef pair<int,int> PII;

// 解题思路: 

const int N=1e5+5;

int main() {
	map<int,int> m;
	int n;
	cin>>n;
	for(int i=1;i<=n;i++) {
		int temp;
		cin>>temp;
		m[temp]++; // temp作为索引,键值+1
	}
	bool flag=false;
	// 遍历map中的所有元素,迭代器的方法遍历
	for(auto it=m.begin();it!=m.end();it++) {
		if(it->second>n/2) {
			flag=true;
			cout<<it->first;
		}
	}
	if(flag==false) cout<<"no";
	return 0;
}

2. 桶排序

• 当数据入桶后其实就相当于已经排好了序，我们可以从元素最小值遍历到最大值，又因为桶中的元素代表着这个元素出现的次数，那么出现了多少次我们就输出多少次这个元素，又因为是从小到大遍历的，所以倒桶的过程就是桶排序
• 桶排序的时间复杂度是$O(n)$，其中n是元素个数

#include<bits/stdc++.h>
#define x first
#define y second

using namespace std;

typedef long long ll;
typedef pair<int,int> PII;

// 解题思路: 假设每个元素的大小范围是[1,1000],我们准备一个大小足够的桶
 
const int N=1e3+5; 
int a[N];

int main() {
	int n;
	cin>>n;
	while(n--) {
		int temp;
		cin>>temp;
		// 入桶
		a[temp]++;
	}
	// 倒桶的过程即为排序,不是真正的排好序
	// 从小到大遍历下标,即less规则排序
	// 从大到小遍历下标,即greater规则排序
	for(int i=1;i<=1000;i++) {
		// 如果i这个数字出现过
		if(a[i]) {
			for(int j=a[i];j>0;j--) {
				// 输出a[i]次,因为a[i]代表i出现的次数
				cout<<i<<' ';
			}
		}	
	}
	return 0;
}

打赏