給定一個(gè)無(wú)序數(shù)組和一個(gè)常數(shù)k，在數(shù)組中查找指定條件的兩個(gè)數(shù)，使得兩數(shù)之和等于k。
簡(jiǎn)單的方法就不說(shuō)了，直接上比較理想的方法：
先對(duì)數(shù)組排序，然后兩個(gè)游標(biāo)，一個(gè)在數(shù)組頭，一個(gè)在數(shù)組尾，然后兩頭遍歷。
代碼如下：
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 }
算法復(fù)雜度為O(nlogn)。
擴(kuò)展，如果不是兩個(gè)數(shù)字而是三個(gè)數(shù)字呢？其實(shí)還是可以利用上面的方法做的，只不過(guò)得稍微轉(zhuǎn)化一下問(wèn)題，因?yàn)橐蟮氖侨齻€(gè)數(shù)，而我們可以把三個(gè)數(shù)的和 a[i] + a[j] + a[r] = k轉(zhuǎn)化為兩個(gè)數(shù)的和a[j] + a[r] = k - a[i]，這樣，其實(shí)只需要在上層while循環(huán)中添加一層for循環(huán)，每次變化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 }
上面算法復(fù)雜度很明顯為O(nlogn + n
2) = O(n
2)。
現(xiàn)在問(wèn)題又變了，假如數(shù)組中不存在某兩個(gè)數(shù)的和為k，現(xiàn)在要找出某兩個(gè)數(shù)的和最接近k，那么怎么做呢？其實(shí)答案非常簡(jiǎn)單，只需要在兩個(gè)游標(biāo)i和j遍歷過(guò)程中順便用一個(gè)變量delta記錄|a[i] + a[j] - t|即可，代碼略。
posted on 2012-09-05 22:28
myjfm 閱讀(746)
評(píng)論(0) 編輯 收藏 引用 所屬分類(lèi):
算法基礎(chǔ)