題目：請給出一個運行時間為Θ(nlgn)的算法，使之能在給定一個由n個整數構成的集合S和另一個整數x時，判斷出S中是否存在有兩個其和等於x的元素。 解題思路： 直觀的方法是直接計算集合中兩兩元素的和，然後判斷是否存在x，但時間復雜度為Θ(n^2)，不符合題目的要求，也不是一個好的解決問題的方法，下面兩種方法要好一些： 第一種是《算法導論》的教師手冊上提供的思路，構建一個輔助集合S'，通過查找輔助集合S'和原集合合並後的集合中是否有重復的元素來判斷，具體步驟如下： 1）對集合S進行排序 2）構建輔助集合S'，S'={z：z=x-y，y∈S}，也就是說S'中的元素是x減去集合S中的元素生成 3）對集合S'進行排序 4）移除集合S中重復的元素，只保留一個，也就是說使集合S中的元素唯一。對集合S'中做同樣的處理。 5）合並集合S和S' 6）當且僅當合並的集合中存在連續的位置上出現相同的的值時，集合S中存在兩個數的和為x。（基本直譯） 這個解題思路是有問題，而且如果簡單從字面意思理解的話，這個思路是錯誤的，在某些情況下是不正確的。下面一一列出這個思路存在的問題： a. 在生成輔助集合S'之後，才開始將集合S中的重復元素去掉只保留一個，這樣S'中也會有同樣的重復元素，為什麼不在生成輔助結合S'之前做呢？如果在第1步之後做的話，S'中的元素也是唯一的了，減少重復的工作 b. 第3步完全沒有必要，因為S在第1步中已經排好序了，所以生成的S'集合也是排好序的了，只是排序的方式不同。如果集合S是升序排列，則集合S'是降序排列。所以沒有必要再對集合S'排序，只需在合並的時候稍作處理即可。 c. 第6步中的描述原文是”There exist two elements in S whose sum is exactly x if and only if the same value appears in consecutive positions in the merged output“，如果 從字面意思理解的話，就是只要合並的集合中有重復的元素就證明結合S中存在兩個數的和為x。但是如果這麼理解的話，是不對的，比如集合S={2，3，5， 6}，x=4， 則S'={2, 1，-1，-2}，合並後的集合為{-2， -1， 1， 2， 2， 3， 5， 6}，合並後的結合中存在重復的元素{2, 2}，位置連續並且和為x，但是集合S中並沒有兩個數的和 為x。所以第6步的表述是有問題，要麼是真的錯了，要麼是語音差異理解的有問題。那要怎麼才能正確地確定呢？就是在合並的集合中必須至少有兩個重復的元素，這時 才能肯定集合S中存在兩個數的和為x。可以證明一下，假設w∈S， y∈S，則集合S'中也存在w∈S，y∈S，所以合並的集合中會有兩個重復的元素w、y。如果有多對解 的話，重復的元素個數會更多。 d. 第4步中將重復的元素唯一化，如果重復的元素的和剛好是x呢？這時豈不是反而弄巧成拙了？比如集合S={2，2，5， 6}，x=4，去除重復的元素，反而錯失了找到兩個數的和為x的機會，而且題目中也沒有要求兩個和為x的元素不能重復。 還有一點需要注意的是，這個思路只是用來確定集合S中是否有兩個元素的和為x，不需要確定是哪兩個元素的和為x。 所以個人認為正確的思路應該是這樣： 1）對集合S進行排序 2）檢查集合S中是否有重復的元素，如果有則判斷重復的元素乘以2（就是兩個相加）是否為x，如果是的話，就找到了，無需做後面的處理；否則移除重復的元素，使集合S 中的元素唯一。 3）構建輔助集合S'，S'={z：z=x-y，y∈S}，也就是說S'中的元素是x減去集合S中的元素生成 4）合並集合S和S' 5）當合並的集合中有兩個或兩個以上的重復元素時，集合S中存在兩個元素的和為x。 接下來確定上面的思路的算法復雜度。第1步的使用歸並排序來完成，時間復雜度為Θ(nlg(n))，第2、3、4、5步的時間復雜度為Θ(n)，合並起來為Θ(nlg(n))。符合題目的要求。 其代碼實現如下所示： [cpp] #include <stdio.h> #include <errno.h> #ifndef INT_MAX #define INT_MAX ((int)(~0U>>1)) #endif #define ARRAY_SIZE(__s) (sizeof(__s) / sizeof(__s[0])) static void merge(int *a, int start, int mid, int end) { int nl = mid - start + 1; int nr = end - mid; int sentinel = INT_MAX; int left[nl + 1], right[nr + 1]; int i, j, k = start; for (i = 0; i < nl; ++i) { left[i] = a[k++]; } /* Set sentinel */ left[i] = sentinel; for (j = 0; j < nr; ++j) { right[j] = a[k++]; } /* Set sentinel */ right[j] = sentinel; i = j = 0; for (k = start; k <= end; ++k) { if (left[i] <= right[j]) { a[k] = left[i++]; } else { a[k] = right[j++]; } } } static void merge_sort(int *a, int start, int end) { int mid; if ((start >= 0) && (start < end)) { mid = (start + end) /2 ; merge_sort(a, start, mid); merge_sort(a, mid + 1, end); merge(a, start, mid, end); } } static int check_exist_x(int *a, int len, int x) { int i, j, k; int last; /* Just for test, should avoid */ int tmp[len]; int collection[2 * len]; int repeats; if (len < 1) { fprintf(stderr, "Too few elements.\n"); return -EINVAL; } merge_sort(a, 0, len - 1); last = 0; /* Remove repeat elements */ for (i = 1; i < len; ++i) { if (a[last] == a[i]) { if ((a[last] << 1) == x) { /* Found */ return 0; } continue; } a[++last] = a[i]; } ++last; /* Form tmp set */ for (i = 0; i < last; ++i) { tmp[i] = x - a[i]; } i = 0; j = last - 1; k = 0; /* Merge */ while ((i < last) && (j >= 0)) { if (a[i] < tmp[j]) { collection[k++] = a[i++]; } else { collection[k++] = tmp[j--]; } } while (i < last) { collection[k++] = a[i++]; } while (j >= 0) { collection[k++] = tmp[j--]; } repeats = 0; /* Check the number of repeat elements */ for (i = 1, j = 0; i < k; ++i, ++j) { if (collection[i] == collection[j]) { ++repeats; } if (repeats >= 2) { return 0; } } return -1; } int main(void) { int source[] = { 7, 5, 2, 4, 6, 1, 5, 3}; int ret; int x = 13; ret = check_exist_x(source, ARRAY_SIZE(source), x); printf("If there are two elements whose sum equals to x? %s.\n", ret < 0 ? "No" : "Yes"); return 0; } 第二種是使用排序+二分查找，具體步驟如下： 1）對集合S進行排序 2）從集合S中選擇一個元素S(i)，計算x與S(i)的差值y=x-S(i)。在集合S中查找除S(i)之外的元素中是否存在y，如果存在，則返回。 3）檢查是否全部元素已遍歷，如果沒有跳到第2步。 接下來確定該思路的復雜度。第1步使用歸並排序來排序，時間復雜度為Θ(nlg(n))；二分查找的時間復雜度為Θ(lg(n))，第2、3步需要遍歷的次數為n，因此第2、3步的時間復雜度為Θ(nlg(n))，因此總的時間復雜度為Θ(nlg(n))，符合題目的要求。 代碼實現如下所示： [cpp] #include <stdio.h> #include <errno.h> #ifndef INT_MAX #define INT_MAX ((int)(~0U>>1)) #endif #define ARRAY_SIZE(__s) (sizeof(__s) / sizeof(__s[0])) static void merge(int *a, int start, int mid, int end) { int nl = mid - start + 1; int nr = end - mid; int sentinel = INT_MAX; int left[nl + 1], right[nr + 1]; int i, j, k = start; for (i = 0; i < nl; ++i) { left[i] = a[k++]; } /* Set sentinel */ left[i] = sentinel; for (j = 0; j < nr; ++j) { right[j] = a[k++]; } /* Set sentinel */ right[j] = sentinel; i = j = 0; for (k = start; k <= end; ++k) { if (left[i] <= right[j]) { a[k] = left[i++]; } else { a[k] = right[j++]; } } } static void merge_sort(int *a, int start, int end) { int mid; if ((start >= 0) && (start < end)) { mid = (start + end) /2 ; merge_sort(a, start, mid); merge_sort(a, mid + 1, end); merge(a, start, mid, end); } } static int binary_search(int *a, int len, int expect, int target) { int left = 0, right = len - 1, mid; do { if (left == expect) { ++left; } if (right == expect) { --right; } mid = (left + right) / 2; if ((mid != expect) && (a[mid] == target)) { return 0; } else if (a[mid] > target) { right = --mid; } else { left = ++mid; } } while (left <= right); return -1; } static int check_exist_x(int *a, int len, int x) { int i; if (!a || len < 2) { fprintf(stderr, "Too few elements.\n"); return -1; } merge_sort(a, 0, len - 1); for (i = 0; i < len; ++i) { if (!binary_search(a, len, i, x - a[i])) { return 0; } } return -1; } int main(void) { int source[] = { 7, 5, 2, 4, 6, 1, 5, 3}; int x = 13; www.2cto.com int ret; ret = check_exist_x(source, ARRAY_SIZE(source), x); printf("If there are two elements whose sum equals to x? %s.\n", ret < 0 ? "No" : "Yes"); return 0; }
