求两个数之和等于某个数
例如 {2, 3, 1, 6, 5, 4, 9, 8}, 10
1.
直接两次循环扫描，时间 O(N ^ 2)
2.
先排序，从两端扫描
时间复杂度是 O(N ^ logN)
3.
从同学那里学到的
首先对和这个数 M ，分配 M + 1 个空间
扫描集合，记录每个数出现的情况
然后扫描 M + 1 的空间，检测出
但是这种方法，在集合中的元素大于 M 时就失效了
另外记录每个数出现的情况，其实也就是对集合进行了排序，
然后对这个辅助空间进行扫描
本质上讲，这种方法和第二种方法是一样的，也是先排序，然后再从两端扫描
只不过这种方法利用了限制信息，也就是说排序算法是基数排序。
时间复杂度是 O(N + M)
空间复杂度是 O(M)
当存在大量集合元素，元素的范围为 0 - 2^(sizeof (int) * 8)-1, M 为任意的，我们可以设定辅助数组的大小为
2^(sizeof (int) * 8)
1 #include <iostream>
2 #include <cstring>
3 using namespace std;
4
5 void foo(int a[], int n, int m)
6 {
7 int* p = new int[m + 1];
8 memset(p, 0, sizeof (*p) * (m + 1));
9 for (int i = 0; i != n; ++i)
10 {
11 ++p[a[i]];
12 }
13 int i = 0, j = m;
14 while (i < j)
15 {
16 if (p[i] != 0 && p[j] != 0)
17 {
18 for (int k = 0; k != p[i] * p[j]; ++k)
19 {
20 cout << i << ' ' << j << endl;
21 }
22 }
23 ++i;
24 --j;
25 }
26 if (i == j && p[i] >= 2)
27 {
28 for (int k = 0; k != p[i] * (p[i] - 1) / 2; ++k)
29 {
30 cout << i << ' ' << i << endl;
31 }
32 }
33 }
34
35 int main()
36 {
37 int a[] = {2, 2, 2, 3, 1, 6, 5, 5, 5, 4, 9, 8};
38 int m = 10;
39 foo(a, sizeof (a) / sizeof (*a), m);
40 return 0;
41 }
posted on 2011-08-03 21:33
unixfy 阅读(307)
评论(0) 编辑 收藏 引用