題目描述
給出一個矩陣mat观蜗，找出所有行都出現(xiàn)的數字，如果有多個衣洁，就輸出最小的那個數墓捻。如果沒有，輸出-1坊夫。
思路點撥
用hashmap維護每個數最后出現(xiàn)的行數砖第，最后在掃一遍hashmap取最小即可。
考點分析
本題對每行去暴力尋找有哪些數出現(xiàn)环凿，顯然不可取梧兼。我們可以換一個思維，對每個數x維護該數最后出現(xiàn)的行數智听，如果遍歷到第i行羽杰，發(fā)現(xiàn)x的最后出現(xiàn)的行數不是i-1，那么我們就可以舍去這個數了到推，最后遍歷一遍所有的數出現(xiàn)的行數是否為n即可考赛。思維的轉變尤其重要，本題也突出了MS的特色莉测。
參考程序
http://www.jiuzhang.com/solution/matrix-finding-number/
/**
* 本參考程序來自九章算法颜骤，由 @斌助教 提供。版權所有捣卤，轉發(fā)請注明出處忍抽。
* - 九章算法致力于幫助更多中國人找到好的工作，教師團隊均來自硅谷和國內的一線大公司在職工程師董朝。
* - 現(xiàn)有的面試培訓課程包括：九章算法班鸠项，系統(tǒng)設計班，算法強化班子姜，Java入門與基礎算法班锈锤，Android 項目實戰(zhàn)班，
* - Big Data 項目實戰(zhàn)班闲询，算法面試高頻題班, 動態(tài)規(guī)劃專題班
* - 更多詳情請見官方網站：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;
}
}
