一亩三分地论坛

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

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

[算法题] G的一道面经

[复制链接] |试试Instant~ |关注本帖
一回头的温柔 发表于 2016-5-4 03:12:46 | 显示全部楼层 |阅读模式

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

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

x
给一个2Dvector表示一个image。如果image中有值为0的pixel,就删除掉该pixel所在的行和列,最后返回一个处理后的新的image。
问下这个题,比如说给的
111
101
111
返回的是
11
11
吗?

这样一来的话边长改变了,具体代码怎么写呢
lakerl 发表于 2016-5-4 22:38:12 | 显示全部楼层
这应该是最差的解法了吧,我用的python:
import numpy as np
a = [[1,1,1,1]
    ,[1,0,1,0]
    ,[1,1,1,1]]
a = np.array(a)
row = 0
col = 0
judge = 0
for i in range(len(a)):
    judge = 0
    for j in range(len(a[0])):
        if a[i][j] == 0:
            judge = 1
            col += 1
    if judge != 0:   
        row += 1
new_row = len(a) - row
new_col = len(a[0]) -col
new_a = np.ones((new_row,new_col))
new_a
回复 支持 反对

使用道具 举报

oh_yee 发表于 2016-5-4 23:20:28 | 显示全部楼层
我想的是先扫一遍, 记录下每个0所在的行、列
这样就知道了有哪些行、列将被删除。
然后再扫一遍原输入, 碰到grid[i][j]在将要被删除的行、列上, 就跳过。
回复 支持 反对

使用道具 举报

lakerl 发表于 2016-5-5 00:02:46 | 显示全部楼层
oh_yee 发表于 2016-5-4 23:20
我想的是先扫一遍, 记录下每个0所在的行、列
这样就知道了有哪些行、列将被删除。
然后再扫一遍原输入, ...

你这样的复杂度应该是O(n2),我后来又想了一个矩阵相乘的方法,复杂度是O(n):
假设你题目里那个矩阵是a,新矩阵的行为row,列为col, 两个初值都为0,a先乘一个size为(len(a[0]),1)的单位矩阵,得到矩阵c=[4,2,4],size是(3,1)(p.s.不方便打矩阵,就将就下吧,也能看懂的),然后对矩阵c逐行遍历,只要碰到等于len(a[0]),(这里是4),row += 1; 然后对a做转置得到矩阵b,(python里直接a.T就ok了),再生成一个size为(len(b[0],1))的单位矩阵c,再b*c,得到矩阵d: [3,2,3,2],size是(4,1),再对d逐行遍历,仍然是只要碰到等于len(a[0]),(这里是4),col += 1. 这样就获得了新矩阵的行列数row,col. row, col中只要有一个是0,返回[], 否则返回size为(row,col)的单位矩阵。
回复 支持 反对

使用道具 举报

lakerl 发表于 2016-5-5 00:03:16 | 显示全部楼层
oh_yee 发表于 2016-5-4 23:20
我想的是先扫一遍, 记录下每个0所在的行、列
这样就知道了有哪些行、列将被删除。
然后再扫一遍原输入, ...

代码:
import numpy as np
a = [[1,1,1,1]
    ,[1,0,1,0]
    ,[1,1,1,1]]
a = np.array(a)
ones_1 = np.ones((len(a[0]),1))
b = np.dot(a,ones_1)
row = 0
col = 0
temp = 0
for i in range(len(b)):
    if b == len(a[0]):
        row += 1
ones_2 = np.ones((len(a.T[0]),1))
c = np.dot(a.T,ones_2)
for j in range(len(c)):
    if c[j] == len(a.T[0]):
        col += 1
row,col
if row == 0 or col == 0:
    ans = []
else:
    ans = np.ones((row,col))
ans
回复 支持 反对

使用道具 举报

oh_yee 发表于 2016-5-5 08:48:12 | 显示全部楼层
lakerl 发表于 2016-5-5 00:02
你这样的复杂度应该是O(n2),我后来又想了一个矩阵相乘的方法,复杂度是O(n):
假设你题目里那个矩阵是a ...

但矩阵乘法不是O(mnp) 吗? 如果是m*n矩阵和n*p矩阵相乘的话。

如果是两个n*n矩阵的话, 时间是O(n^3)
回复 支持 反对

使用道具 举报

lakerl 发表于 2016-5-5 10:12:17 | 显示全部楼层
numpy矩阵乘法不是这个复杂度,具体实现原理我不清楚,但肯定远比o(n3)快,我以前看过相关资料。
回复 支持 反对

使用道具 举报

huai10 发表于 2016-5-5 11:32:41 | 显示全部楼层
lakerl 发表于 2016-5-5 10:12
numpy矩阵乘法不是这个复杂度,具体实现原理我不清楚,但肯定远比o(n3)快,我以前看过相关资料。

做高斯分解后相乘么?
回复 支持 反对

使用道具 举报

lakerl 发表于 2016-5-5 12:59:10 | 显示全部楼层
huai10 发表于 2016-5-5 11:32
做高斯分解后相乘么?

不清楚。这个要看源码了,我以前看过有人做过测试,numpy乘法比两层循环的快很多,想这种通常的数学库,矩阵的计算算法肯定是优化过的。
回复 支持 反对

使用道具 举报

Mark6 发表于 2016-5-5 13:14:04 | 显示全部楼层
本帖最后由 Mark6 于 2016-5-5 13:15 编辑
oh_yee 发表于 2016-5-4 23:20
我想的是先扫一遍, 记录下每个0所在的行、列
这样就知道了有哪些行、列将被删除。
然后再扫一遍原输入, ...

受你的方法的启发。我实习了一下。代码只是最后不用再扫描一下原image,只是算一下删了之后还剩多少行多少列,然后建一个新数组,全部fill 1就好了。不过这是基于只有1和0的情况。

public static int[][] deleteZeroRowCol(int[][] grid){
                if(grid == null || grid[0].length == 0){return new int[][]{};}
                int rowCount = grid.length;
                int colCount = grid[0].length;
                boolean[] rowFlag = new boolean[grid.length];
                boolean[] colFlag = new boolean[grid[0].length];
                for(int i = 0; i < grid.length; i++){
                        for(int j = 0; j < grid[0].length; j++){
                                if(grid(i)[j] == 0){
                                        if(!rowFlag(i)){ rowCount--; rowFlag = true;}
                                        if(!colFlag[j]){ colCount--; rowFlag[j] = true;}
                                }
                        }
                }
                int[][] result = new int[rowCount][colCount];
                for(int[] nums : result){
                        Arrays.fill(nums, 1);
                }
                return result;
        }

}
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-5 23:11

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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