离散化模板

缘起

很多时候, 如果我们要考察一组数字，例如

-1118, 57, 3299, 163, 871,-2,73, -2, 57, 163

我们只关心其在数组中的大小相对顺序, 而不关心其绝对的数值, 则此时离散化就起到了作用.

分析

算法就是排序+去重, 然后找到其排名, 算法复杂度是 O(nlogn)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
#include "stdafx.h"
#include <iostream>
#include <algorithm>

#pragma warning(disable:4996)

//#define LOCAL
using namespace std;

const int MAX_N = 105;

int unique(int *a, int n) // 对含有n个元素的数组a去重, 返回去重后数组的元素的个数
{
	int i,j;
	for (i=0,j=1;j<n;)
	{
		while(a[i]==a[j]) j++;
		if (j<n) a[++i] = a[j];
	}
	return i+1; // 最后去重之后的数组存放在 a[0,...,i]中
}

int pos(int *a, int n, int target) // 二分查找target在a[0,...n)中的索引，即不大于target的最大索引
{
	int lo = 0, hi=  n;
	while(lo<hi)
	{
		int mi = (lo+hi)>>1;
		target<a[mi]?hi=mi:lo=mi+1;
	}
	return --lo;
}

void discrete(int *a, int *x, int n) // 将数组a离散化为x, n是a的长度
{
	int b[MAX_N];
	memcpy(b,a,sizeof(int)*n);
	sort(b, b+n);
	int res = unique(b, n);
	for (int i = 0; i<n; i++) x[i]= pos(b,res,a[i]);
}


int main()
{
#ifdef LOCAL
	freopen("d:\\data.in","r",stdin);
#endif
	int a[] = {-1118, 57, 3299, 163, 871,-2,73, -2, 57, 163};  // 排序之后 -1118 -2 -2 57 57 73 163 163 871 3299 去重之后是  -1118 -2 57 73 163 871 3299
	int x[10];
	discrete(a,x,10);
	puts("离散化之后");
	for (int i = 0; i<10;i++)
	{
		printf("%d ", x[i]); // 0 2 6 4 5 1 3 1 2 4
	}
	return 0;
}