一道在蜻蜓FM面试的时候，出的算法题。题目是让在Young氏矩阵中查询一个数，并把他们的坐标都返回。
一个m x n的Young氏矩阵（Young tableau）是一个m x n的矩阵，其中每一行的数据都从左到右排序，每一列的数据都从上到下排序。Young氏矩阵中可能会有一些∞数据项，表示不存在的元素。所以，Young氏矩阵可以用来存放 r ≦ mn 个有限的数。
在面试的时候，我只想到了大致的思路，并没有写出完整的程序。之后思考了下，当时的思路还不够完整，许多方面都没有考虑到。接下来，我讲给出我之后想通了的两种解法。
二分查找
题目很明显是可以用二分查找来做的，但是关键是如何二分。最先想到的合理方式是，通过左对角线找到的中点arr[n / 2][n / 2]，可以将矩阵分为4个部分。
如果target小于arr[n / 2][n / 2]，那么我们可以排除的矩阵的后1 / 4的部分。之后留给我们是剩下的3 / 4，我们应该如何处理呢？这个也是我面试的时候没有想清楚的。
如果我们仍然把剩下的部分当做一个整体，那么我们处理起来就会有一些问题，因为我们并不能用已有的知识来进行进一步的优化。如果我们将剩下的这个图形拆解开来会不会有更好的效果呢？假设对于一个矩阵，我们去掉的是右下方的1 / 4(下图中的黄色部分)，我们将剩下的图形当做两个长方形来看待。
这两个长方形也完全符合Young氏矩阵的概念。所以我们依旧可以用上述方法来继续求解。
如果target大于arr[n / 2][n / 2]，同理我们使用另外的两个长方形进行求解。
如果相等的话，首先将当前元素的位置加入最后的解集，继续找的范围是左下方的矩阵和右上方的矩阵(严格递增)。
但是在求出结果后，我们会发现有一些元素的位置会重复出现在最后的位置中，并且没有什么特别的规律。所以这里采用了老土的set去重，希望如果有想法的可以在我的博客下留言。
using pos = pair<int, int>;
using vi = vector<int>;
using vvi = vector<vi>;
class Solution {
public:
vector<pos> findingNumInYoungMatrix(vvi &map, int target) {
int height, width;
vector<pos> ret;
if((height = map.size()) == 0) return ret;
if((width = map[0].size()) == 0) return ret;
set<pos> t;
worker(map, target, t, make_pair(0, 0), make_pair(height - 1, width - 1));
return vector<pos> { t.begin(), t.end() };
}
void worker(vvi &map, int target, set<pos> &ret, pos lt, pos rb) {
if(lt.first > rb.first || lt.second > rb.second) return;
pos mid = make_pair((lt.first + rb.first) / 2, (lt.second + rb.second) / 2);
int mid_val = map[mid.first][mid.second];
if(target == mid_val) {
ret.insert(mid);
worker(map, target, ret, make_pair(mid.first + 1, lt.second), make_pair(rb.first, mid.second - 1));
worker(map, target, ret, make_pair(lt.first, mid.second + 1), make_pair(mid.first - 1, rb.second));
}
else if(target > mid_val) {
worker(map, target, ret, make_pair(mid.first + 1, lt.second), rb);
worker(map, target, ret, make_pair(lt.first, mid.second + 1), rb);
}
else {
worker(map, target, ret, lt, make_pair(mid.first - 1, rb.second));
worker(map, target, ret, lt, make_pair(rb.first, mid.second - 1));
}
}
};
右上角比较
这个解法是我的一个同学在听完这个题目后和我说的。我们可以通过用target和右上角的元素进行比较。如果target小于当前元素的话，我们就可以去掉竖排，因为竖排的元素一定大于当前元素；反之，target大于当前元素，我们可以同理去掉横排的元素。要是如果相等的话，加入解集，并且将两排同时去掉。
感觉整个程序的逻辑应该比上面的要简单一些，但是在一些答的数据集中，应该还是上面这种做法效率更加高，因为每次去掉的元素至少是1 / 4。