离散化思想

给出一列数字，在有些情况下，这些数字的值的绝对大小不重要，而相对大小很重要。如班级的分数有99 98 97 95 96，排名为 1 2 3 5 4。

离散化是一种数据处理的技巧，它把分布广而稀疏的数据转换位密集分布，从而能够让算法更快速、更省空间地处理。

离散化地步骤：排序，离散化，归位。

如：               4000 210 11 45 800

  数组下标为  1         2     3    4   5

将它们存储在结构体中，在进行排序。

---------------------

排序：            11     45    210  800 4000

                        3          4       2     5     1

------------------------

离散化：       1        2         3        4      5

数组的下标：3         4         2       5       1

----------------------

归位  ：        5          3          1        2    4     

数组下标       1          2           3       4     5

下面是代码解析：

  

   

    

     

    
    

     

      #define _CRT_SECURE_NO_WARNINGS 1
     
    
   

    

     

    
    

     

      //离散化
     
    
   

    

     

    
    

     

      #include<bits/stdc++.h>
     
    
   

    

     

    
    

     

      using 
      namespace std;
     
    
   

    

     

    
    

     

      const 
      int N = 
      500010;
     
    
   

    

     

    
    

     

      struct 
      data1 {
     
    
   

    

     

    
    

     
	
      int val;
     
    
   

    

     

    
    

     
	
      int id; 
      // 用坐标代替
     
    
   

    

     

    
    

     

      }olda[N];
     
    
   

    

     

    
    

     

      int newa[N];
     
    
   

    

     

    
    

     

      bool cmp(data1 x, data1 y) { 
      return x.val < y.val; }
     
    
   

    

     

    
    

     

      int main() {
     
    
   

    

     

    
    

     
	
      int n;
     
    
   

    

     

    
    

     
	
      scanf(
      "%d", &n);
     
    
   

    

     

    
    

     
	
      for (
      int i = 
      1; i <= n; i++) {
     
    
   

    

     

    
    

     
		
      scanf(
      "%d", &olda[i].val);
     
    
   

    

     

    
    

     

      		olda[i].id = i;
     
    
   

    

     

    
    

     

      	}
     
    
   

    

     

    
    

     
	
      sort(olda + 
      1, olda + 
      1 + n, cmp); 
      //排序
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     
	
      //离散化 + 归位 
     
    
   

    

     

    
    

     
	
      for (
      int i = 
      1; i <= n; i++) {
     
    
   

    

     

    
    

     

      		newa[olda[i].id] = 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函数实现离散化：

lower_bound() 和 unique()函数实现离散化。

查找第1个等于或大于x的元素：lower_bound()且等于x。位置如 pos = lower_bound(a,a+n,x) - a。

unique()函数：

unique是 c++标准模板库STL中十分实用的函数之一，使用此函数需要#include <algorithm>头文件

该函数的作用是“去除”容器或者数组中相邻元素的重复出现的元素
(1) 这里的去除并非真正意义的erase，而是将重复的元素放到容器的末尾，返回值是去重之后的尾地址。 

注意这一点：它只对相邻的元素。
(2) unique针对的是相邻元素，所以对于顺序错乱的数组成员，或者容器成员，需要先进行排序，可以调用std::sort()函数。

  

   

    

     

    
    

     

      #define _CRT_SECURE_NO_WARNINGS 1
     
    
   

    

     

    
    

     

      //离散化
     
    
   

    

     

    
    

     

      #include<bits/stdc++.h>
     
    
   

    

     

    
    

     

      using 
      namespace std;
     
    
   

    

     

    
    

     

      const 
      int N = 
      5000010;
     
    
   

    

     

    
    

     

      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 + n + 
      1);
      //默认是从小到大 less<int>()
     
    
   

    

     

    
    

     
	
      int cnt = n; 
      // 记录个数 调用unique函数时，是去重的数组
     
    
   

    

     

    
    

     
	
      //cnt = unique(olda + 1, olda + 1 + n) - (olda + 1);//返回不重复的尾元素 如 1 1 2 3 调用函数后 1 2 3 1 返回 3 
     
    
   

    

     

    
    

     
	
      for (
      int i = 
      1; i <= cnt; i++) {
     
    
   

    

     

    
    

     

      		newa[i] = 
      lower_bound(olda + 
      1, olda + 
      1 + n, newa[i]) - olda;
     
    
   

    

     

    
    

     

      	}
     
    
   

    

     

    
    

     
	
      for (
      int i = 
      1; i <= cnt; i++) {
     
    
   

    

     

    
    

     
		
      printf(
      "%d ", newa[i]);
     
    
   

    

     

    
    

     

      	}
     
    
   

    

     

    
    

     
	
      return 
      0;
     
    
   

    

     

    
    

     

      }