剑指offer？

1. 在一个m*n二维数组中，每一行都按照从左到右的递增顺排序，每一列都按照从上到下的顺序排序，请完成一个函数，输入这样一个二维数组和一个整数，判断数组中是否含有该整数。
1 2 8 9
2 4 9 12
4 7 9 12
6 8 11 15

杨氏矩阵。这题有更好的做法吗？O(m+n)是最好的吗？网上说的分治法只对m=n的情况吧。

 1 bool find(vector<vector<int> > &arr, int t) {
 2     if (arr.empty() || arr[0].empty()) return false;
 3     int m = arr.size(), n = arr[0].size();
 4 
 5     int x = 0, y = n - 1;
 6     while (x < m && y >= 0) {
 7         if (t == arr[x][y]) return true;
 8         else if (t > arr[x][y]) x++;
 9         else y--;
10     }      
11     return true;
12 }

变种1：

求第k个数，我觉得能想出来用堆就不错了。n路归并，O(klgn)，就是维护一个堆。

 1 struct Num {
 2     int val, row, col;
 3     Num(int r, int c, int v) : val(v), row(r), col(c) {}
 4 };
 5 
 6 class Comparator {
 7 public:
 8     bool operator() (Num &n1, Num &n2) {
 9         return n1.val > n2.val;
10     }
11 };
12 
13 int findKthSmallest(vector<vector<int> > &arr, int k) {
14     if (arr.empty() || arr[0].empty()) return false;
15     int m = arr.size(), n = arr[0].size();
16 
17     priority_queue<Num, vector<Num>, Comparator> mins;
18     for (int i = 0; i < k && i < n; ++i) {
19         mins.push(Num(0, i, arr[0][i]));
20     }
21     for (--k; k; --k) {
22         Num top = mins.top(); mins.pop(); 
23         if (top.row < n - 1) {
24             mins.push(Num(top.row + 1, top.col, arr[top.row + 1][top.col]));
25         }     
26     }
27     return mins.top().val;
28 }

这问题线性的比较难了。http://www.quora.com/How-can-you-efficiently-determine-the-k-th-maximum-element-in-a-MxN-sorted-matrix

可以用一个k大小的堆，O(klgk)。每次pop掉一个数，比如arr[i][j]，然后把arr[i+1][j]和arr[i][j+1]进堆，代价是要有一个数组维护这个数是不是已经在堆里了。

变种2：

给定两个有序数组，长度分别为m和n，分别取出一个数再求和，共有m*n个数，求第k个和（从小到大）。

还是组成一个杨氏矩阵。

 1 int findKthSmallest2(vector<int> &arr1, vector<int> &arr2, int k) {
 2     if (arr1.empty() || arr2.empty()) return false;
 3     int m = arr1.size(), n = arr2.size();
 4 
 5     priority_queue<Num, vector<Num>, Comparator> mins;
 6     for (int i = 0; i < k && i < n; ++i) {
 7         mins.push(Num(0, i, arr1[0] + arr2[i]));
 8     }
 9     
10     for (--k; k; --k) {
11         Num top = mins.top(); mins.pop(); 
12         if (top.row < n - 1) {
13             mins.push(Num(top.row + 1, top.col, arr1[top.row + 1] + arr2[top.col]));
14         }     
15     }
16 
17     return mins.top().val;
18 }

2 输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}，则重建二叉树并输出它的后序遍历序列。（本题可以直接输出来，不用先还原出二叉树)