一亩三分地论坛

 找回密码
 获取更多干货,去instant注册!

扫码关注一亩三分地公众号
查看: 846|回复: 11
收起左侧

[算法题] 如何高效找出2d数组里面数字一样的行和列

[复制链接] |试试Instant~ |关注本帖
iammajian 发表于 2016-5-2 04:44:48 | 显示全部楼层 |阅读模式

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看,没有帐号?获取更多干货,去instant注册!

x
给出一个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.
谢谢!
malc 发表于 2016-5-2 06:10:46 | 显示全部楼层
本帖最后由 malc 于 2016-5-2 07:45 编辑

更新:
  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.         bool colFlag = false;
  13.         for (i = 0; i < arr.size(); i++) {
  14.                 int target=arr[0][i];
  15.                 if(set.find(target)==set.end())
  16.                         continue;
  17.                 for (j = 0, colFlag = true; j < arr[i].size() && colFlag; j++)
  18.                         colFlag = (arr[j][i] == target);
  19.                 if(colFlag)
  20.                         return true;
  21.         }
  22.         return false;
  23. }
复制代码
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.         if (rowFlag == false)
  9.                 return false;

  10.         bool colFlag = false;
  11.         for (i = 0; i < arr.size() && (!colFlag); i++) {
  12.                 for (j = 0, colFlag = true; j < arr[i].size() && colFlag; j++)
  13.                         colFlag = (arr[j][i] == target);
  14.         }
  15.         return rowFlag & colFlag;
  16. }
复制代码
回复 支持 0 反对 1

使用道具 举报

zj45499 发表于 2016-5-2 05:19:16 | 显示全部楼层
本帖最后由 zj45499 于 2016-5-2 05:23 编辑

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

评分

1

查看全部评分

回复 支持 1 反对 0

使用道具 举报

 楼主| iammajian 发表于 2016-5-2 05:34:51 | 显示全部楼层
zj45499 发表于 2016-5-2 05:19
elimination

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

这个答案很不错,谢谢分享!
回复 支持 反对

使用道具 举报

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

这个思路好像很简洁。
回复 支持 反对

使用道具 举报

zj45499 发表于 2016-5-2 07:06:45 | 显示全部楼层
yueliu2366 发表于 2016-5-2 06:57
这个思路好像很简洁。

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

使用道具 举报

 楼主| iammajian 发表于 2016-5-2 07:26:43 | 显示全部楼层
这一题确实输入只是一个2d的array,并不知道target
回复 支持 反对

使用道具 举报

malc 发表于 2016-5-2 07:45:44 | 显示全部楼层
iammajian 发表于 2016-5-2 07:26
这一题确实输入只是一个2d的array,并不知道target

稍微改改就好了,更新了
回复 支持 反对

使用道具 举报

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

哦,如果是这样的话,就得多个hashset了
回复 支持 反对

使用道具 举报

gaohannk 发表于 2016-5-6 10:15:27 | 显示全部楼层
yueliu2366 发表于 2016-5-2 08:22
哦,如果是这样的话,就得多个hashset了

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

使用道具 举报

malc 发表于 2016-5-6 11:56:02 | 显示全部楼层
gaohannk 发表于 2016-5-6 10:15
为什么多个hashset,set是干什么用的,如果一行和一列数字都相同,不可能有两行,每行数字都一样,但这两 ...

有道理!那时候没想到这点,所以space可以做到O(1)
回复 支持 反对

使用道具 举报

yueliu2366 发表于 2016-5-6 19:33:11 | 显示全部楼层
gaohannk 发表于 2016-5-6 10:15
为什么多个hashset,set是干什么用的,如果一行和一列数字都相同,不可能有两行,每行数字都一样,但这两 ...

你说得对,用不着set。只需要用额外两个变量记录相同的行和列就可以了。但其实用了set,这个set最多只有一个元素,空间复杂度也还是O(1)
回复 支持 反对

使用道具 举报

本版积分规则

请点这里访问我们的新网站:一亩三分地Instant.

Instant搜索更强大,不扣积分,内容组织的更好更整洁!目前仍在beta版本,努力完善中!反馈请点这里

关闭

一亩三分地推荐上一条 /5 下一条

手机版|小黑屋|一亩三分地论坛声明 ( 沪ICP备11015994号 )

custom counter

GMT+8, 2016-12-3 08:35

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

快速回复 返回顶部 返回列表