离散化C++

离散化（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;
}