Cantor数组问题：
已知数组A[0...N-1]乱序着前N个正整数，现统计后缀数组A[i+1...N-1]中小于元素A[i]的数目，并存放在数组C[i]中。则C数组称为Cantor数组。
如给定数组：4，6，2，5，1，3。得到的Cantor数组为：3，4，1，2，1，0。
生成Cantor数组程序实现：
1 //生成Cantor数组 2 void CantorCreate(int* A,int* C,int size){ 3 for(int i=0;i<size;i++){ 4 C[i] = 0; 5 for(int j=i+1;j<size;j++){ 6 if(A[j]<A[i]) 7 C[i]++; 8 } 9 } 10 }
运行结果：
由Cantor数组得到原数组，需要一个顺序数组B辅助，A[i] = B[C[i]]。程序实现如下：
1 //由cantor数组求原数组，时间复杂度为O(n^2),空间复杂度为O(n) 2 void CantorReverse(const int* C,int* A,int size){ 3 vector<int> B(size); 4 for(int i=0;i<size;i++){ 5 B[i] = i + 1; 6 } 7 for(int i=0;i<size;i++){ 8 A[i] = B[C[i]]; 9 B.erase(B.begin()+C[i]); 10 } 11 }
但上面实现时间复杂度为O(n^2)，空间复杂度为O(n)。现在允许改变Cantor数组，空间复杂度可降为O(1)。
1 //cantor数组可变,由cantor数组求原数组，空间复杂度为O(1) 2 void CantorReverse2(int* C,int* A,int size){ 3 memset(A,0,sizeof(int)*size); 4 int i,j; 5 for(i=0;i<size;i++){ 6 for(j=0;j<size;j++){ 7 if(A[j] != 0) 8 continue; 9 if(C[j] == 0) 10 break; 11 C[j]--; 12 } 13 A[j] = i+1; 14 } 15 }
运行结果：
总体程序代码实现：
1 /*************************************** 2 FileName Cantor.cpp 3 Author : godfrey 4 CreatedTime : 2016/5/4 5 ****************************************/ 6 #include <iostream> 7 #include <cstring> 8 #include <vector> 9 #include <algorithm> 10 #include <stdio.h> 11 #include <stdlib.h> 12 13 using namespace std; 14 //生成Cantor数组 15 void CantorCreate(int* A,int* C,int size){ 16 for(int i=0;i<size;i++){ 17 C[i] = 0; 18 for(int j=i+1;j<size;j++){ 19 if(A[j]<A[i]) 20 C[i]++; 21 } 22 } 23 } 24 //由cantor数组求原数组，时间复杂度为O(n^2),空间复杂度为O(n) 25 void CantorReverse(const int* C,int* A,int size){ 26 vector<int> B(size); 27 for(int i=0;i<size;i++){ 28 B[i] = i + 1; 29 } 30 for(int i=0;i<size;i++){ 31 A[i] = B[C[i]]; 32 B.erase(B.begin()+C[i]); 33 } 34 } 35 //cantor数组可变,由cantor数组求原数组，空间复杂度为O(1) 36 void CantorReverse2(int* C,int* A,int size){ 37 memset(A,0,sizeof(int)*size); 38 int i,j; 39 for(i=0;i<size;i++){ 40 for(j=0;j<size;j++){ 41 if(A[j] != 0) 42 continue; 43 if(C[j] == 0) 44 break; 45 C[j]--; 46 } 47 A[j] = i+1; 48 } 49 } 50 int main() 51 { 52 // int a[] = {4,6,2,5,3,1}; 53 // int size = sizeof(a)/sizeof(int); 54 // int* c = new int[size]; 55 // cout<<"原数组 : "<<endl; 56 // for(int i=0;i<size;i++){ 57 // cout<<a[i]<<" "; 58 // } 59 // cout<<endl; 60 // CantorCreate(a,c,size); 61 // cout<<"Cantor数组 : "<<endl; 62 // for(int i=0;i<size;i++){ 63 // cout<<c[i]<<" "; 64 // } 65 // cout<<endl; 66 67 int c[] = {3,4,1,2,1,0}; 68 int size = sizeof(c)/sizeof(int); 69 int* a = new int[size]; 70 cout<<"Cantor数组 : "<<endl; 71 for(int i=0;i<size;i++){ 72 cout<<c[i]<<" "; 73 } 74 cout<<endl; 75 CantorReverse2(c,a,size); 76 cout<<"原数组 : "<<endl; 77 for(int i=0;i<size;i++){ 78 cout<<a[i]<<" "; 79 } 80 cout<<endl; 81 return 0; 82 }
转载请注明出处：
C++博客园：godfrey_88