题目地址：

https://www.lintcode.com/problem/matrix-finding-number/description

给定一个二维矩阵，求每行都出现过的数中最小的那个。如果不存在，则返回$-1$。

思路是哈希表。先用一个哈希表$S$存第$0$行的所有数，然后开始从第$1$行开始遍历矩阵，每次都将$S$中存在的数加入另一个哈希表$S^{\prime }$，接着将$S^{\prime }$赋值给$S$，对$S^{\prime }$再新开个哈希表赋值给它。最后一行遍历完毕之后，$S$里就存的是每一行都出现过的数。遍历之找到最小值即可。不存在则返回$-1$。代码如下：

import java.util.HashSet; import java.util.Iterator; import java.util.Set; public class Solution { /** * @param mat: The matrix * @return: The answer */ public int findingNumber(int[][] mat) { // Write your code here Set<Integer> set = new HashSet<>(); for (int i : mat[0]) { set.add(i); } Set<Integer> cur = new HashSet<>(); for (int i = 1; i < mat.length; i++) { for (int j = 0; j < mat[0].length; j++) { if (set.contains(mat[i][j])) { cur.add(mat[i][j]); } } set = cur; cur = new HashSet<>(); } int res = Integer.MAX_VALUE; Iterator<Integer> it = set.iterator(); while (it.hasNext()) { int num = it.next(); res = Math.min(res, num); } return res == Integer.MAX_VALUE ? -1 : res; } }

时间复杂度$O(mn)$，空间$O(n)$。