题目描述
给出一个矩阵mat，找出所有行都出现的数字，如果有多个，就输出最小的那个数。如果没有，输出-1。
思路点拨
用hashmap维护每个数最后出现的行数，最后在扫一遍hashmap取最小即可。
考点分析
本题对每行去暴力寻找有哪些数出现，显然不可取。我们可以换一个思维，对每个数x维护该数最后出现的行数，如果遍历到第i行，发现x的最后出现的行数不是i-1，那么我们就可以舍去这个数了，最后遍历一遍所有的数出现的行数是否为n即可。思维的转变尤其重要，本题也突出了MS的特色。
参考程序
http://www.jiuzhang.com/solution/matrix-finding-number/
/**
* 本参考程序来自九章算法，由 @斌助教 提供。版权所有，转发请注明出处。
* - 九章算法致力于帮助更多中国人找到好的工作，教师团队均来自硅谷和国内的一线大公司在职工程师。
* - 现有的面试培训课程包括：九章算法班，系统设计班，算法强化班，Java入门与基础算法班，Android 项目实战班，
* - Big Data 项目实战班，算法面试高频题班, 动态规划专题班
* - 更多详情请见官方网站：http://www.jiuzhang.com/?source=code
*/
public class Solution {
/**
* @param mat: The matrix
* @return: The answer
*/
Integer min(Integer a, Integer b) {
if(a < b)
return a;
else
return b;
}
public int findingNumber(int[][] mat) {
// Write your code here
Map<Integer, Integer> map = new HashMap<Integer, Integer>();
for(int i = 0; i < mat.length; i++) {
for(int j = 0; j < mat[i].length; j++) {
if(map.containsKey(mat[i][j])) {
if(map.get(mat[i][j]) == i - 1) {
map.put(mat[i][j], i);
}
}
else {
if(i == 0) {
map.put(mat[i][j], 0);
}
}
}
}
Integer ans = 10007;
for (Map.Entry<Integer, Integer> it : map.entrySet()) {
if(it.getValue() == mat.length - 1) {
ans = min(ans, it.getKey());
}
}
if(ans == 10007)
ans = -1;
return ans;
}
}
