离散化

离散化手工编码

#include<bits/stdc++.h>
const int N = 500010;                  //自己定义一个范围
struct data{
  int val;                             //元素的值
  int id;                              //元素的位置
}olda[N];                              //离散化之前的原始数据
int newa[N];                           //离散化后的结果
bool cmp(data x,data y){ return x.val < y.val; }    //用于sort()
int main(){
  int n; scanf("%d",&n);               //读元素个数
  for(int i=1;i<=n;i++) {
    scanf("%d",&olda[i].val);          //读元素的值
    olda[i].id = i;                    //记录元素的位置
  }
  std::sort(olda+1,olda+1+n,cmp);      //对元素的值排序
  for(int i=1;i<=n;i++){               //生成 newa[]
    newa[olda[i].id]=i;                //这个元素原来的位置在olda[i].id，把它的值赋为i，i是离散化后的新值
    if(olda[i].val == olda[i-1].val)   //若两个元素的原值相同，把新值赋为相同
      newa[olda[i].id] = newa[olda[i-1].id];
  }
  for(int i=1;i<=n;i++) printf("%d ",newa[i]);     //打印出来看看
  return 0;
}

笔记：数据的具体数值转化成相对的排名输出，算法快捷，更节省空间

用STL函数实现离散化

#include<bits/stdc++.h>
using namespace std;
const int N = 500010;                               // 自己定义一个范围
int olda[N]; // 离散化前
int newa[N]; // 离散化后
int main(){
  int n; scanf("%d",&n);
  for(int i=1;i<=n;i++) {
    scanf("%d",&olda[i]);                          //读元素的值
    newa[i] = olda[i];
  }
  sort(olda+1,olda+1+n); //排序
  int cnt = n;
//cnt = unique(olda+1,olda+1+n)-(olda+1);         //去重，cnt是去重后的数量
  for(int i=1;i<=cnt;i++)                         //生成 newa[]
    newa[i]=lower_bound(olda+1,olda+1+n,newa[i])-olda;
  //查找相等的元素的位置，这个位置就是离散化后的新值    lower_bound(数组名，范围，查找的数）-数组名
  for(int i=1;i<=cnt;i++) printf("%d ",newa[i]);  //打印出来看看
  printf("\n cnt=%d",cnt);
  return 0;
}

笔记：使用lower_bound()函数查找数字下标储存在新的数组中