简介

离散化是程序设计中一个常用的技巧，它可以有效的降低时间和空间复杂度，例如有如下的一个数组。

1, 23424, 21472313246768, 6594, 95, 0, 65535313

如果将这些数作为数组的下标来保存对应的属性，那么就需要一个很大的数组，但有时只需要知道相对大小，那么就可以使用数组离散化。例如，上述的数据离散化之后就成了如下的值。

1, 4, 6, 3, 2, 0, 5

也就是只体现了相对大小。

实现

简单来说，就是先排个序，然后再重新编号，例如 {10000000, 10, 2000, 20, 300, 20} 重新编码为 {5, 0, 4, 1, 3, 1} 数组，也就是编码从 0 开始，最大为 N-1 其中 N 表示元素数。

这里介绍两种方法，注意上述重复元素的处理。

方法 1

先排序然后重新编号。

struct data_node {
    int value;
    int index;
};

static int cmp_inc(const void* a, const void* b)
{
    const struct data_node *aa = a;
    const struct data_node *bb = b;
    return aa->value - bb->value;
}

void array_discrete(int *ret, int *arr, int size)
{
    struct data_node *nodes;

    nodes = malloc(sizeof(struct data_node) * size);
    for (int i = 0; i < size; i++) {
        nodes[i].index = i;
        nodes[i].value = arr[i];
    }
    qsort(nodes, size, sizeof(struct data_node), cmp_inc);

    ret[nodes[0].index] = 0;
    for (int i = 1; i < size; i++) {
        if (nodes[i].value == nodes[i - 1].value) {
            ret[nodes[i].index] = ret[nodes[i - 1].index];
        } else {
            ret[nodes[i].index] = i;
        }
    }
    free(nodes);
}

方法 2

先排序然后再使用二分查找计算。

// 返回有多少个元素小于target，例如 {1, 2, 3, 4, 4, 5} 4->3 3->2
static int lower_bound(const int *nums, int length, int target)
{
    int left, right, mid;

    left = 0;
    right = length - 1;
    while (left <= right) {
        mid = left + (right - right) / 2;
        if (nums[mid] < target) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    return left;
}

static int cmp_int_inc(const void* a, const void* b)
{
    return (*(int*)a - *(int*)b);
}

void array_discrete(int *ret, int *arr, int size)
{
    memcpy(ret, arr, sizeof(int) * size);
    qsort(arr, size, sizeof(int), cmp_int_inc);
    for (int i = 0; i < size; i++) {
        ret[i] = lower_bound(arr, size, ret[i]);
    }
}

离散化数组介绍

简介 #

实现 #

方法 1 #

方法 2 #

简介

实现

方法 1

方法 2