记录
14:29 2024-3-4
1.离散化
如果数据范围太大，但是数据个数并不是很多，可以离散化后，保留了数据的大小关系
问题的范围虽然定义在集合，但是只涉及其中的有限数值，并且与数值的绝对大小无关(只把这些数值作为代表，或只与他们的相对顺序有关)
点击查看代码
void discrete() { //离散化
// 数据从1开始
sort(a + 1, a + n + 1);
for(int i = 1; i <=n; i++) { //也可以使用STL中的unique函数
if (i == 1 || a[i] != a[i - 1])
b[++m] = a[i];
}
//a[i] 是输入的数组 排序后 b[m]是无重复的数组
}
int query(int x) { //查询x映射为哪个1~m之间的整数
return lower_bound(b + 1, b + m + 1, x) - b;
}
使用unique和一种模板写法
点击查看代码
// a输入的数组
vector<int> vec;
void discreate() {
sort(vec.begin(), vec.end());
vec.erase(unique(vec.begin(), vec.end()), vec.end());
}
// 查询x映射为哪个数 这里是映射从1开始
int query(int x) {
return lower_bound(vec.begin(), vec.end(), x) - vec.begin() + 1;
}
// 另一种写法 从leetcode 125双周赛来的
// https://leetcode.cn/contest/biweekly-contest-125/ranking/
// 抄的来源是 @ujimatsu_chiya https://leetcode.cn/u/ujimatsu_chiya/ (叠甲，再有源头我就不知道了)
template <typename T>
struct HashTable {
vector<T> val;
void add(T x) { val.push_back(x); }
void init() {
sort(all(val));
val.erase(unique(all(val)), val.end());
}
int query(T x) { return lower_bound(ALL(val), x) - val.begin() + 1; }
T operator[](const int t) const { return val[t - 1]; }
int size() { return val.size(); }
void clear(){val.clear();}
};