基础思维——离散化(附例题)

(21) 2024-03-26 22:01:01

引论

离散化:
把无限空间中有限的个体映射到有限的空间中去,以此提高算法的时空效率。具体来说,离散化是在不改变数据相对大小的条件下,对数据进行相应的缩小。

例如:
原数据:1,999,100000000000,15;处理后:1,3,4,2;
原数据:{100,200},{20,50000},{1,400};
处理后:{3,4},{2,6},{1,5};

例如:
在一个坐标轴很长(>1e8),给你1e4个坐标,询问某一个点,坐标比它小的点有多少。我们只需要知道他们之间的相对大小就可以,这就需要离散化。

两种离散化方法(去重与不去重)
1、离散化——去重

理解思路
①、在 book 数组中记录出现的元素大小 tot。
②、对 book 数组进行从小到大排序,利用 unique函数对 book 数组进行去重,得到去重后的数组大小 c 。

//unique(book,book+n);
//前一个是当序列的相邻的数据相同时,删除相邻相同的数字。
sort(book, book+tot);
//必须先排序
int c = unique(book, book+tot) - book;

③、再对 book 数组进行从小到大排序,在 book 数组下找原数组 num 对应的下标即为离散数组 ans。

for (int i=0; i<n; i++) { 
   
    ans[i] = lower_bound(book, book+c, num[i])-book;
}

离散化——去重:整合代码

#include<bits/stdc++.h>
using namespace std;
int ans[100010]={ 
   0};//离散化后数组
int num[100010], book[100010];
int n;

int main(){ 
   
	int n;
	scanf("%d", &n);
	for (int i=0; i<n; i++) { 
   
	    scanf("%d",&num[i]);
	    book[i] = num[i];
	}
	 
	int c = unique(book, book+n) - book;
	sort(book , book
THE END

发表回复