Skip to content

Discretization

Introduction

Discretization is a data processing technique that can be essentially viewed as a form of hashing, ensuring that the data maintains its original total/partial order relationship after hashing.

In simpler terms, when certain data cannot be conveniently used as array indices due to their large size or unsupported type, and only the relative magnitude between elements affects the final result, we can process the original data based on their rankings—this is discretization.

Data that can be discretized includes large integers, floating-point numbers, strings, etc.

Implementation

Discretizing an array and performing queries is a common application scenario.

Method One

Typically, the original array contains duplicate elements, which are usually discretized into the same value.

The method is as follows:

  1. Create a copy of the original array.
  2. Sort the copy in ascending order.
  3. Remove duplicates from the sorted copy.
  4. Find the position of each element of the original array in the copy; this position is its ranking and serves as the discretized value.

1
2
3
4
5
6
7
8
// arr[i] is the original array, with indices in the range [1, n]

for (int i = 1; i <= n; ++i)  // step 1
  tmp[i] = arr[i];
std::sort(tmp + 1, tmp + n + 1);                          // step 2
int len = std::unique(tmp + 1, tmp + n + 1) - (tmp + 1);  // step 3
for (int i = 1; i <= n; ++i)                              // step 4
  arr[i] = std::lower_bound(tmp + 1, tmp + len + 1, arr[i]) - tmp;

The STL algorithms used in the reference implementation can be found in STL Algorithms.

Similarly, we can also discretize a std::vector:

1
2
3
4
5
6
// std::vector<int> arr;
std::vector<int> tmp(arr);  // tmp is a copy of arr
std::sort(tmp.begin(), tmp.end());
tmp.erase(std::unique(tmp.begin(), tmp.end()), tmp.end());
for (int i = 0; i < n; ++i)
  arr[i] = std::lower_bound(tmp.begin(), tmp.end(), arr[i]) - tmp.begin();

Method Two

Depending on the problem requirements, sometimes identical elements need to be discretized into different values based on their input order.

In this case, using the std::lower_bound() function becomes more challenging, and a different approach is needed:

  1. Create a copy of the original array while recording the position of each element.
  2. Sort the copy by value in ascending order; when values are equal, sort by occurrence order in ascending order.
  3. Assign the discretized values back to the original array.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
struct Data {
  int idx, val;

  bool operator<(const Data& o) const {
    if (val == o.val)
      return idx < o.idx;  // When values are equal, the earlier element gets a smaller discretized value
    return val < o.val;
  }
} tmp[MAXN];  // std::pair can also be used

for (int i = 1; i <= n; ++i) tmp[i] = Data{i, arr[i]};
std::sort(tmp + 1, tmp + n + 1);
for (int i = 1; i <= n; ++i) arr[tmp[i].idx] = i;

Complexity

For Method One, deduplication has a complexity of \(O(n)\), sorting has a complexity of \(O(n \log n)\), and the final \(n\) lookups have a complexity of \(O(n \log n)\).

For Method Two, sorting has a complexity of \(O(n \log n)\).

Thus, the total time complexity for both methods is \(O(n \log n)\).

The space complexity is \(O(n)\).

Exercises

本页面最近更新：，更新历史
发现错误？想一起完善？ 在 GitHub 上编辑此页！
本页面贡献者：OI-wiki
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用