点击刷新
在《编程珠玑》上看到的，开篇第一个问题，有很多数，小于一个MAXNUM，没有重复的，怎么排序最快。
答案是位图排序. 如果某一位不为0，那么这一位存代表一个数，位数（在序列中的位置）代表这个数。
比方说这些数都存在数组a，然后利用一个数组b，b初始状态各位都为0，然后读取a，如果a[1]=2，那么b[2]为1，a[3]=6,那么b[6]=1。
实现如下：
1 #include <iostream> 2 #include <fstream> 3 #include<stdlib.h> 4 #include<vector> 5 #define MAXNUM 200 6 int Isood(int n); 7 8 using namespace std; 9 10 11 int main(void) 12 { 13 vector<int> v1,v2; 14 int n; 15 cin>>n; 16 int m; 17 m=MAXNUM; 18 while(n) 19 { 20 int t; 21 cin>>t; 22 v1.push_back(t); 23 n--; 24 } 25 26 while(m) 27 { 28 v2.push_back(0); 29 m--; 30 } 31 32 for(int i=0;i<v1.size();i++) 33 { 34 v2[v1[i]-1]=1; 35 } 36 37 for(int i=0;i<v2.size();i++) 38 { 39 if(v2[i]) 40 { 41 cout<<i+1;+ 42 } 43 } 44 45 }
© 著作权归作者所有
举报
发表评论
0/200
