給定一個無序數組和一個常數k，在數組中查找指定條件的兩個數，使得兩數之和等于k。
簡單的方法就不說了，直接上比較理想的方法：
先對數組排序，然后兩個游標，一個在數組頭，一個在數組尾，然后兩頭遍歷。
代碼如下：
1 int cmp(const void *a, const void *b) {
2 return *(int *)a - *(int *)b;
3 }
4
5 struct result {
6 int first;
7 int second;
8 };
9
10 result find_two_numbers(int *a, int n, int k) {
11 int i = 0, j = n - 1;
12 result res = {-1, -1};
13
14 if (a == NULL || n < 2) {
15 return res;
16 }
17
18 qsort(a, n, sizeof(int), cmp);
19
20 while (i < j) {
21 if (a[i] + a[j] == k) {
22 res.first = i;
23 res.second = j;
24 return res;
25 } else if (a[i] + a[j] < k) {
26 i++;
27 } else {
28 j--;
29 }
30 }
31 return res;
32 }
算法復雜度為O(nlogn)。
擴展，如果不是兩個數字而是三個數字呢？其實還是可以利用上面的方法做的，只不過得稍微轉化一下問題，因為要求的是三個數，而我們可以把三個數的和 a[i] + a[j] + a[r] = k轉化為兩個數的和a[j] + a[r] = k - a[i]，這樣，其實只需要在上層while循環中添加一層for循環，每次變化k的值為k1 = k - a[i]即可，代碼如下：
1 struct result_three {
2 int first;
3 int second;
4 int third;
5 };
6
7 result_three find_three_numbers(int *a, int n, int k) {
8 int i, j, r;
9 result_three res = {-1, -1, -1};
10
11 if (a == NULL || n < 3) {
12 return res;
13 }
14
15 qsort(a, n, sizeof(int), cmp);
16
17 for (i = 0; i < n; ++i) {
18 int k1 = k - a[i];
19 j = 0, r = n - 1;
20 while (j < r) {
21 if (j == i) {
22 j++;
23 continue;
24 }
25 if (r == i) {
26 r--;
27 continue;
28 }
29
30 if (a[j] + a[r] == k1) {
31 res.first = i;
32 res.second = j;
33 res.third = r;
34 return res;
35 } else if (a[j] + a[r] < k1) {
36 j++;
37 } else {
38 r--;
39 }
40 }
41 }
42 return res;
43 }
上面算法復雜度很明顯為O(nlogn + n
2) = O(n
2)。
現在問題又變了，假如數組中不存在某兩個數的和為k，現在要找出某兩個數的和最接近k，那么怎么做呢？其實答案非常簡單，只需要在兩個游標i和j遍歷過程中順便用一個變量delta記錄|a[i] + a[j] - t|即可，代碼略。
posted on 2012-09-05 22:28
myjfm 閱讀(761)
評論(0) 編輯 收藏 引用 所屬分類:
算法基礎