坐标离散化 - (sunznx) 振翅飞翔
10 October 2019

在介绍 “坐标离散化” 之前,先来介绍一下坐标离散化的使用场景。在 《编程珠玑》 里面提到使用 “位图排序” 算法,效率是 O(n)
位图排序算法可以用如下伪代码来描述:

$maxNum = max($arr);
$bitmap = array_fill(0, $maxNum+1, 0);
foreach ($arr as $num) {
    $bitmap[$num] = 1;
}

$sortedArr = [];
$idx = 0;
for ($i = 0; $i <= $maxNum; $i++) {
    if ($bitmap[$i] > 0) {
        $sortedArr[$idx++] = $i;
    }
}

这样看,时间效率确实是 O(n) ,这会存在两个问题

  1. 要求数组的每个元素都是 >=0
  2. “效率” 取决于数组中最大的元素,例如数组是 [5, 3, 99999] ,那么在遍历的时候需要走 99999+1 次(下标从 0 开始)

假设我们有办法将 [5, 3, 99999] 这个数组映射成 [1, 0, 2] 就简单了,这就是坐标离散化的好处。

当然,坐标离散化的使用场景并不是用来解决排序,因为坐标离散化本身就需要一次排序…

相关的代码在
https://github.com/sunznx/php-datastruct/blob/master/src/Discretize/Discretize.php
https://github.com/sunznx/php-datastruct/blob/master/tests/discretize_test.php