输入: 一个最多包含n=10^7的正整数文件，每个正整数都要小于n.
输出: 按升序
约束: 最多有(大约)1MB的内存空间可用.1. 如果不缺内寸, 如何使用一个具有库的语言来实现一种排序算法以表示和排序集合? C++
  set/vector
1 #include "stdafx.h"
2#include <set>
3#include <vector>
4#include <algorithm> // sort
5#include <iostream>
6using namespace std;
7
8void setSort()
9 {
10 set<int> s;
11 set<int>::iterator j;
12 s.insert(rand());
13 for (j = s.begin(); j != s.end(); ++j)
14 cout<< *j<<"\n";
15 }
16
17void vectorSort()
18{
19 vector<int> v;;
20 vector<int>::iterator vj;
21 v.push_back(rand());
22 sort(v.begin(), v.end());
23 for (vj = v.begin(); vj != v.end(); ++vj)
24 cout<<*vj<<"\n";
25}C
qsort
1void qsort (void* base, size_t num, size_t size,
2 int (*compar)(const void*,const void*)); 2. 如何使用位逻辑运算(例如与, 或, 移位)来实现向量?1个int 32bit, 4字节, 所以N个数的话就需要 1+N/32 ~ 10^7/32 = 312500, --> 312500 *4 = 1.192 ~1.25 MB如果用0表示无此位置数据，1表示有此位置数据,可用如下字符串来表示集合 {3,5,7,8}: 1101 0100.
SET/CLR
1#define BITSPERWORD 32
2#define SHIFT 5
3#define MASK 0x1F
4#define N 10000000
5int a[1+N/BITSPERWORD];
6
7void SET(int i) { a[i>>SHIFT] |= (1<<(i & MASK)); }
8void CLR(int i) { a[i>>SHIFT] &= ~(1<<(i & MASK)); } ps: a[i>>SHIFT] 对应 1+N/32;
1<<(i & MASK) 对应到此位置有数据.
3. 生成小于N且没有重复的整数
randint
1int randint(int l, int r)
2{
3 return (rand() % (r-1) + l);
4}
4. 可以用k趟算法完成对最多n个小于n的无重复正整数的排序, 时间kn, 空间n/k.
5. 上面的程序都是不存在错误处理和限定.
程序员拿到题目应该多思考, 而不是直接code, 其实有些题目在了解了之后往往比想象的来的简单~~
|