离散化（Discretization）是一种将连续数据映射到离散值的技术，常用于将大数据范围压缩到较小范围，例如将数值映射到索引。离散化在算法竞赛中常用于处理数值范围较大但数据量较小的问题（如区间问题、统计问题等）。
以下是离散化的模板和示例：
1. 离散化的基本步骤
- 排序：将所有需要离散化的值排序。
- 去重：去除重复的值。
- 映射：通过二分查找将原始值映射到离散化后的索引。
2. 离散化模板
2.1 使用 std::vector 和 std::unique
#include <iostream>
#include <vector>
#include <algorithm>
// 离散化函数
std::vector<int> discretize(std::vector<int>& nums) {
// 1. 排序
std::vector<int> sorted_nums = nums;
std::sort(sorted_nums.begin(), sorted_nums.end());
// 2. 去重
auto last = std::unique(sorted_nums.begin(), sorted_nums.end());
sorted_nums.erase(last, sorted_nums.end());
// 3. 映射
std::vector<int> result(nums.size());
for (size_t i = 0; i < nums.size(); i++) {
result[i] = std::lower_bound(sorted_nums.begin(), sorted_nums.end(), nums[i]) - sorted_nums.begin();
}
return result;
}
int main() {
std::vector<int> nums = {100, 200, 50, 100, 300, 50};
// 离散化
std::vector<int> discretized = discretize(nums);
// 输出结果
std::cout << "Original: ";
for (int num : nums) {
std::cout << num << " ";
}
std::cout << std::endl;
std::cout << "Discretized: ";
for (int num : discretized) {
std::cout << num << " ";
}
std::cout << std::endl;
return 0;
}
输出：
Original: 100 200 50 100 300 50
Discretized: 1 2 0 1 3 0
2.2 离散化后还原原始值
如果需要还原离散化后的值，可以通过离散化数组进行映射。
#include <iostream>
#include <vector>
#include <algorithm>
// 离散化函数
std::pair<std::vector<int>, std::vector<int>> discretizeWithMap(std::vector<int>& nums) {
// 1. 排序
std::vector<int> sorted_nums = nums;
std::sort(sorted_nums.begin(), sorted_nums.end());
// 2. 去重
auto last = std::unique(sorted_nums.begin(), sorted_nums.end());
sorted_nums.erase(last, sorted_nums.end());
// 3. 映射
std::vector<int> result(nums.size());
for (size_t i = 0; i < nums.size(); i++) {
result[i] = std::lower_bound(sorted_nums.begin(), sorted_nums.end(), nums[i]) - sorted_nums.begin();
}
return {result, sorted_nums};
}
int main() {
std::vector<int> nums = {100, 200, 50, 100, 300, 50};
// 离散化
auto [discretized, map] = discretizeWithMap(nums);
// 输出结果
std::cout << "Original: ";
for (int num : nums) {
std::cout << num << " ";
}
std::cout << std::endl;
std::cout << "Discretized: ";
for (int num : discretized) {
std::cout << num << " ";
}
std::cout << std::endl;
std::cout << "Map: ";
for (int num : map) {
std::cout << num << " ";
}
std::cout << std::endl;
// 还原离散化后的值
std::cout << "Reconstructed: ";
for (int num : discretized) {
std::cout << map[num] << " ";
}
std::cout << std::endl;
return 0;
}
输出：
Original: 100 200 50 100 300 50
Discretized: 1 2 0 1 3 0
Map: 50 100 200 300
Reconstructed: 100 200 50 100 300 50
3. 离散化的应用场景
3.1 区间问题
离散化常用于处理区间问题，例如区间合并、区间查询等。
#include <iostream>
#include <vector>
#include <algorithm>
// 区间合并
std::vector<std::pair<int, int>> mergeIntervals(std::vector<std::pair<int, int>>& intervals) {
if (intervals.empty()) return {};
// 离散化
std::vector<int> nums;
for (const auto& interval : intervals) {
nums.push_back(interval.first);
nums.push_back(interval.second);
}
auto [discretized, map] = discretizeWithMap(nums);
// 区间合并
std::sort(intervals.begin(), intervals.end());
std::vector<std::pair<int, int>> merged;
for (const auto& interval : intervals) {
if (merged.empty() || merged.back().second < interval.first) {
merged.push_back(interval);
} else {
merged.back().second = std::max(merged.back().second, interval.second);
}
}
return merged;
}
int main() {
std::vector<std::pair<int, int>> intervals = {{1, 3}, {2, 6}, {8, 10}, {15, 18}};
// 区间合并
auto merged = mergeIntervals(intervals);
// 输出结果
std::cout << "Merged Intervals: ";
for (const auto& interval : merged) {
std::cout << "[" << interval.first << ", " << interval.second << "] ";
}
std::cout << std::endl;
return 0;
}
输出：
Merged Intervals: [1, 6] [8, 10] [15, 18]
3.2 统计问题
离散化可以用于统计某个范围内数据的频率。
#include <iostream>
#include <vector>
#include <algorithm>
// 统计频率
std::vector<int> countFrequency(std::vector<int>& nums) {
// 离散化
auto [discretized, map] = discretizeWithMap(nums);
// 统计频率
std::vector<int> freq(map.size(), 0);
for (int num : discretized) {
freq[num]++;
}
return freq;
}
int main() {
std::vector<int> nums = {100, 200, 50, 100, 300, 50};
// 统计频率
auto freq = countFrequency(nums);
// 输出结果
std::cout << "Frequency: ";
for (int count : freq) {
std::cout << count << " ";
}
std::cout << std::endl;
return 0;
}
输出：
Frequency: 2 2 1 1
4. 总结
- 离散化的核心步骤是排序、去重和映射。
- 离散化可以用于处理区间问题、统计问题等。
- 通过离散化，可以将大数据范围压缩到较小范围，提高算法效率。
