G的一道面经

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

这样一来的话边长改变了，具体代码怎么写呢

这应该是最差的解法了吧，我用的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

我想的是先扫一遍， 记录下每个0所在的行、列
这样就知道了有哪些行、列将被删除。
然后再扫一遍原输入， 碰到grid[i][j]在将要被删除的行、列上， 就跳过。

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)的单位矩阵。

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[i] == 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

lakerl 发表于 2016-5-5 00:02
你这样的复杂度应该是O(n2),我后来又想了一个矩阵相乘的方法，复杂度是O(n)：
假设你题目里那个矩阵是a ...

但矩阵乘法不是O（mnp） 吗？ 如果是m＊n矩阵和n＊p矩阵相乘的话。

如果是两个n＊n矩阵的话， 时间是O（n^3)

numpy矩阵乘法不是这个复杂度，具体实现原理我不清楚，但肯定远比o(n3)快，我以前看过相关资料。

lakerl 发表于 2016-5-5 10:12
numpy矩阵乘法不是这个复杂度，具体实现原理我不清楚，但肯定远比o(n3)快，我以前看过相关资料。

做高斯分解后相乘么？

huai10 发表于 2016-5-5 11:32
做高斯分解后相乘么？

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

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)[i]){ rowCount--; rowFlag[i] = true;}
                                        if(!colFlag[j]){ colCount--; rowFlag[j] = true;}
                                }
                        }
                }
                int[][] result = new int[rowCount][colCount];
                for(int[] nums : result){
                        Arrays.fill(nums, 1);
                }
                return result;
        }

}[/i][/i]