1. 给定一个包含n个整数的数组a和一个整数x，判断数组中是否存在两个元素相加刚好等于x
2. 反转数对：对于一个数组A[1...n]，n个元素都各不相同。如果i < j, 同时A[i] > A[j]，就称为A的一个反转数对。在O(n*lg(n))的时间内找到A有多少反转数对。
这两个题目都可以使用分治的思想，关键是在O(n)的时间内merge。这两题并不容易联想到用分治，主要在于，merge的时候，还要进行一次类似merge_sort一样的排序才能在O(n)内完成对原问题的merge，拐了点弯，不太容易想到。
上源码：
第一题：
1 #include <iostream> 2 #include <limits> 3 4 using namespace std; 5 6 int x = 5; 7 8 bool merge(int a[], int p, int q, int r) 9 { 10 int i = p; int j = r - 1; 11 while (i < q && j >= q) 12 { 13 int asum = a[i] + a[j]; 14 if (asum == x) 15 return true; 16 else if (asum > x) 17 j--; 18 else 19 i++; 20 } 21 22 int* L = new int[q - p + 1]; 23 int* R = new int[r - q + 1]; 24 25 for (int i = 0; i < q - p; i++) 26 L[i] = a[p + i]; 27 for (int i = 0; i < r - q; i++) 28 R[i] = a[q + i]; 29 30 L[q - p] = numeric_limits<int>::max(); 31 R[r - q] = numeric_limits<int>::max(); 32 33 i = 0; j = 0; 34 35 for (int k = p; k < r; k++) 36 { 37 if (L[i] < R[j]) 38 { 39 a[k] = L[i]; 40 i++; 41 } 42 else 43 { 44 a[k] = R[j]; 45 j++; 46 } 47 } 48 49 delete[] L; 50 delete[] R; 51 return false; 52 } 53 54 bool merge_find(int a[], int p, int r) 55 { 56 if (r - p <= 1) 57 return false; 58 int q = (p + r) / 2; 59 if (merge_find(a, p, q)) 60 return true; 61 if (merge_find(a, q, r)) 62 return true; 63 if (merge(a, p, q, r)) 64 return true; 65 return false; 66 } 67 68 int main(int argc, char** argv) 69 { 70 int a[] = { 1, 1, 3, 5, 3, 5}; 71 72 bool flag = merge_find(a, 0, 6); 73 74 cout << flag << endl; 75 76 return 0; 77 }
第二题：
1 #include <iostream> 2 #include <limits> 3 4 using namespace std; 5 6 int merge(int a[], int p, int q, int r) 7 { 8 int invnum = 0; 9 int j = q; 10 for (int i = p; i < q; i++) 11 { 12 while (j < r && a[j] < a[i]) 13 { 14 j++; 15 } 16 invnum += j - q; 17 } 18 19 int* L = new int[q - p + 1]; 20 int* R = new int[r - q + 1]; 21 22 for (int i = 0; i < q - p; i++) 23 L[i] = a[p + i]; 24 for (int i = 0; i < r - q; i++) 25 R[i] = a[q + i]; 26 27 L[q - p] = numeric_limits<int>::max(); 28 R[r - q] = numeric_limits<int>::max(); 29 30 int i = 0; 31 j = 0; 32 33 for (int k = p; k < r; k++) 34 { 35 if (L[i] < R[j]) 36 { 37 a[k] = L[i]; 38 i++; 39 } 40 else 41 { 42 a[k] = R[j]; 43 j++; 44 } 45 } 46 47 delete[] L; 48 delete[] R; 49 return invnum; 50 } 51 52 int merge_find_inverse(int a[], int p, int r) 53 { 54 if (r - p <= 1) 55 return 0; 56 int q = (p + r) / 2; 57 int n1 = merge_find_inverse(a, p, q); 58 int n2 = merge_find_inverse(a, q, r); 59 int n3 = merge(a, p, q, r); 60 return n1 + n2 + n3; 61 } 62 63 int main(int argc, char** argv) 64 { 65 int a[] = { 3, 2, 1}; 66 67 int flag = merge_find_inverse(a, 0, 3); 68 69 cout << flag << endl; 70 71 return 0; 72 }
与Merge Sort相关的两题,布布扣,bubuko.com
原文：http://www.cnblogs.com/tiancaiye/p/3652104.html