Divide and Conquer题解

第一题

You are interested in analyzing some hard-to-obtain data from two separate databases. Each database contains n numerical values, so there are 2n values total and you may assume that no two values are the same. You’d like to determine the median of this set of 2n values, which we will define here to be the nth smallest value.

However, the only way you can access these values is through queries to the databases. In a single query, you can specify a value k to one of the two databases, and the chosen database will return the kth smallest value that it contains. Since queries are expensive, you would like to compute the median using as few queries as possible.

Give an algorithm that finds the median value using at most ????????????(????) queries. 问题描述:表示存在两个相同大小的数组，设每个数组大小为 k，这两个数组都是未排序的， 返回这两个数组中第 k 小的数，同时要求时间复杂度是????????????(????)。

a1[k],a2[k] //k 表示数组个数 SortK(k, start1, end1, start2, end2) 1: if k==1 then

伪代码如下：

a1[k],a2[k] //k 表示数组个数 
SortK(k, start1, end1, start2, end2)
1: if k==1 then
2:    min(a1[start1],a2[start2])
3: else
4:    index1 = k/2 + start1 - 1
5:    index2 = start2 + k - k/2 - 1
6:    if a1[index1] < a2[index2] then
7:        SortK(k – k/2, start1 + k/2, end1, start2, start2 + k - k/2)
8:    else
9:        SortK(k/2, start1, start1 + k/2, start2+ k - k/2, end2)
10:   end if
11: end if

图解如下：

证明正确性

在进行两个数组排序的过程中，每次分别取最中间的数进行比较，然后把一个数组拆分两个数组分别和另一个数组拆分出来的两个数组进行匹配。

1. 如果第一个数组中 a1[k/2-1]大于第二个数组中 a2[k-k/2-1]则表示，第 k 大的值一定在a1[k/2-1]的左半部分数组中或者在 a2[k-k/2-1]的右半部分数组中。所以只需要对这部分进行比较即可。

2. 如果第一个数组中 a1[k/2-1]小于第二个数组中 a2[k-k/2-1]则表示，第 k 大的值一定在a1[k/2-1]的右半部分数组中或者在 a2[k-k/2-1]的左半部分数组中。所以只需要对这部分进行比较即可。

3. 通过上面 1)和 2)递归会减少一半的数量，直到两个数组都只剩下一个值。通过运行发现可以正确查找出第 k 大的值，所以是正确的。

第二题

Given a binary tree, suppose that the distance between two adjacent nodes is 1, please give a solution to find the maximum distance of any two node in the binary tree.

问题描述:给出一个二叉树，求出二叉树两个节点之间的最大距离。

伪代码如下：

maxNum = -1 //maxNum 记录最大距离 
maxDistance(root)
1: datal = 0, datar = 0
2: if root == NULL then
3:    break;
4: if root->lchild != NULL then
5:     datal = maxDistance(root->lchild) + 1
6: if root->rchild != NULL then
7:     datar = maxDistance(root->rchild) + 1
8: if datal + datar > maxNum then
9:     maxNum = datal + datar
10:end if
11:return max(datal,datar)

图解如下：

证明正确性 ：

通过分治算法把一个大问题转化为小问题，也就是说每次节点只通过比较当前的最大距离与其两个子节点的最大距离之和的大小来更新当前的最大距离。知道遍历完所有的节点。 在验证其正确性时，编写了相应的代码进行运行，发现在输入测试用例之后能够正确运行处 相应的结果。

时间复杂度：

这道题主要是分别把当前最大距离和当前节点对应的左右子树最大距离之和进行比较，然后更新最大距离。????(????) = ????????????????(????) 所以通过求解可知最后的时间复杂度为 ????????????????(????)。

第三题

Consider an n-node complete binary tree T , where n = 2d − 1 for some d. Each node v of T is labeled with a real number xv. You may assume that the real numbers labeling the nodes are all distinct. A node v of T is a local minimum if the label xv is less than the label xw for all nodes w that are joined to v by an edge.

You are given such a complete binary tree T , but the labeling is only specified in the following implicit way: for each node v, you can determine the value xv by probing the node v. Show how to find a local minimum of T using only log(????) probes to the nodes of T .

问题描述:给出一个完全二叉树，求出一个局部最小值，使得该节点比与他连接的所有 节点都小，同时使得时间复杂度为log (????)。

伪代码如下：

FindMin(root)
1: if root->lchild == NULL && root->rchild == NULL then
2: return root->data
3: if root->lchild != NULL && root->lchild->data < root->data then
4:     return FindMin(root->lchild)
5: else
6:     if root->rchild != NULL && root->rchild->data < root->data then
7:         return FindMin(root->rchild)
8: end if
9: return root->data

图解如下：

证明正确性

     完全二叉树的特点是如果其右子树的深度为 j，则其左子树的深度必为 j 或 j+1。所以首 先判断:

1. 如果节点的左子节点和右子节点都为空时则返回节点自身的 data。

2. 如果存在左子节点，同时左子节点的 data 小于其父节点的 data，说明该父节点的 data一定不是局部最小值，则继续向下走最坏的情况就是左子节点是整棵树的叶子节点时，其对应的 data 还是小于其父节点的 data，此时该叶子节点则是局部最小值。

3. 如果左子节点的 data 大于其父节点的 data，但是存在右子节点而且右子节点的 data小于其父节点的 data，继续向下走，与 2)相似。

4. 如果节点小于其所对应的子节点，则该节点就是其局部最小值。

   从上面的步骤可以看出，最后程序会返回一个节点保证该节点比其周围的节点都小，即为该范围内的局部最小值。

时间复杂度：????(????) = log (????)