如何高效找出2d数组里面数字一样的行和列

给出一个nxn大小的2d数组，请问如何高效(O(mn))得找出x such that 有一行和一列的所有数字都是x? 如果找不到返回-1.
例子：
0 1 3 2
1 1 1 1
4 1 9 8
4 1 2 1
这个数组里面，第二行和第二列所有数字都是1，返回1.
如果把第一行第二个数字改成非1的数字，那么我们就找不到这样的数字了，返回-1.
谢谢！

更新：

1. bool findRowColumn(vector<vector<int>> &arr) {
   
2.         bool rowFlag = false;
   
3.         std::unordered_set<int> set;
   
4.         size_t i, j;
   
5.         for (i = 0; i < arr.size(); i++) {
   
6.                 int target=arr[i][0];
   
7.                 for (j = 1, rowFlag = true; j < arr[i].size() && rowFlag; j++)
   
8.                         rowFlag = (arr[i][j] == target);
   
9.                 if(rowFlag)
   
10.                         set.emplace(target);
    
11.         }
    
12. 
    
13.         bool colFlag = false;
    
14.         for (i = 0; i < arr.size(); i++) {
    
15.                 int target=arr[0][i];
    
16.                 if(set.find(target)==set.end())
    
17.                         continue;
    
18.                 for (j = 0, colFlag = true; j < arr[i].size() && colFlag; j++)
    
19.                         colFlag = (arr[j][i] == target);
    
20.                 if(colFlag)
    
21.                         return true;
    
22.         }
    
23.         return false;
    
24. }

复制代码

1.逐行搜索是否有一行全为x,O(mn)
2.逐列搜索是否有一列全为x,O(mn)
3.判断这两个标志是否都是true

1. bool findRowColumn(vector<vector<int>> &arr, int target) {
   
2.         bool rowFlag = false;
   
3.         size_t i, j;
   
4.         for (i = 0; i < arr.size() && (!rowFlag); i++) {
   
5.                 for (j = 0, rowFlag = true; j < arr[i].size() && rowFlag; j++)
   
6.                         rowFlag = (arr[i][j] == target);
   
7.         }
   
8. 
   
9.         if (rowFlag == false)
   
10.                 return false;
    
11. 
    
12.         bool colFlag = false;
    
13.         for (i = 0; i < arr.size() && (!colFlag); i++) {
    
14.                 for (j = 0, colFlag = true; j < arr[i].size() && colFlag; j++)
    
15.                         colFlag = (arr[j][i] == target);
    
16.         }
    
17.         return rowFlag & colFlag;
    
18. }

复制代码

elimination

1. x such that 有一行和一列的所有数字都是 x?
<=> 至少有一行的数字是一样的 并且 至少有一列的数字是一样的

2. 两个map分别记录对应的这一行和这一列是否是一样的 初始化全部为 "true"

3. 扫描整个表 把左第一列和上第一行作为reference 如果当前位置的值不相等就把对应map的行和列值设置为 false
表大的话可以优化下比如碰到false的这一整行/列都跳过, 不过不改变BigO就是了.

4. 最后扫描两个map看是否符合两个map中至少有一个true. 如果有的话随便从这行或者这列中取一个值输出 没有的话输出 -1

O(mn)

https://gist.github.com/coderant/39d014b9b0b5c645150ecf74d933cb38

zj45499 发表于 2016-5-2 05:19
elimination

1. x such that 有一行和一列的所有数字都是 x?

这个答案很不错，谢谢分享！

malc 发表于 2016-5-2 06:10
1.逐行搜索是否有一行全为x,O(mn)
2.逐列搜索是否有一列全为x,O(mn)
3.判断这两个标志是否都是true

这个思路好像很简洁。

yueliu2366 发表于 2016-5-2 06:57
这个思路好像很简洁。

我理解的题目的意思是并没有提供 int target 这个值.
如果连这个都提供了不是O(mn)随便写么

这一题确实输入只是一个2d的array，并不知道target

iammajian 发表于 2016-5-2 07:26
这一题确实输入只是一个2d的array，并不知道target

稍微改改就好了，更新了

zj45499 发表于 2016-5-2 07:06
我理解的题目的意思是并没有提供 int target 这个值.
如果连这个都提供了不是O(mn)随便写么

哦，如果是这样的话，就得多个hashset了

yueliu2366 发表于 2016-5-2 08:22
哦，如果是这样的话，就得多个hashset了

为什么多个hashset，set是干什么用的，如果一行和一列数字都相同，不可能有两行，每行数字都一样，但这两行的数字不一样。