求兩個數(shù)之和等于某個數(shù)
例如 {2, 3, 1, 6, 5, 4, 9, 8}, 10
1.
直接兩次循環(huán)掃描，時間 O(N ^ 2)
2.
先排序，從兩端掃描
時間復(fù)雜度是 O(N ^ logN)
3.
從同學(xué)那里學(xué)到的
首先對和這個數(shù) M ，分配 M + 1 個空間
掃描集合，記錄每個數(shù)出現(xiàn)的情況
然后掃描 M + 1 的空間，檢測出
但是這種方法，在集合中的元素大于 M 時就失效了
另外記錄每個數(shù)出現(xiàn)的情況，其實也就是對集合進行了排序，
然后對這個輔助空間進行掃描
本質(zhì)上講，這種方法和第二種方法是一樣的，也是先排序，然后再從兩端掃描
只不過這種方法利用了限制信息，也就是說排序算法是基數(shù)排序。
時間復(fù)雜度是 O(N + M)
空間復(fù)雜度是 O(M)
當(dāng)存在大量集合元素，元素的范圍為 0 - 2^(sizeof (int) * 8)-1, M 為任意的，我們可以設(shè)定輔助數(shù)組的大小為
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 閱讀(339)
評論(0) 編輯 收藏 引用