데이터 의 이산 화

일부 데이터 자 체 는 매우 커서, 자신 은 배열 의 아래 표 로 대응 하 는 속성 을 저장 할 수 없습니다.
만약 이때 이 데이터 의 상대 적 인 속성 만 필요 하 다 면 이 를 이산 화 처리 할 수 있다!
이산 화: 데 이 터 는 그들 간 의 상대 적 인 크기 와 만 관련 되 고 구체 적 인 것 과 무관 할 때 이산 화 할 수 있다.
예컨대
91054 와 520143 의 역순 대 개 수 는 같다.설치 4 개 수: 1234567, 123456789, 12345678, 123456 정렬: 123456 & 1234567 & 12345678 & 123456789           =>     1     <        2       <        3       <        4 그러면 이 네 개 수 는 2, 4, 3, 1 이 라 고 할 수 있다.
STL 알고리즘 을 사용 하여 분 산 됩 니 다. 사고: 먼저 정렬 한 다음 에 중복 요 소 를 삭제 한 다음 에 색인 요소 가 분 산 된 후에 대응 하 는 값 입 니 다.분 산 된 서열 이 a [n] 이 고 b [n] 은 서열 a [n] 의 사본 이 라 고 가정 하면 상기 세 단계 에 대응 합 니 다.

sort(sub_a,sub_a+n);
  
int size=unique(sub_a,sub_a+n)-sub_a;//size         
  
for(i=0;i<n;i++)
	a[i]=lower_bound(sub_a,sub_a+size,a[i])-sub_a + 1;//k b[i]         
  
세 번 째 단계 에 대해 이산 화 후 서열 이 0, 1, 2,..., size - 1 이면 lowerbound, 1, 2, 3,..., size 는 upperbound, 그 중 lowerbound 는 b [i] 보다 작 지 않 은 값 의 지침 을 되 돌려 줍 니 다. upperbound 는 b [i] 보다 큰 값 의 지침 을 되 돌려 줍 니 다. 물론 이 문제 에서 도 lower 를 사용 할 수 있 습 니 다.bound 그리고 1 을 더 해서 upperbound 같은 결 과 는 둘 다 정렬 을 위 한 것 입 니 다.STL 이산 화 를 사용 하여 코드 의 양 을 크게 줄 이 고 구조 가 상당히 뚜렷 하 다.