CS Algo Question - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>CS - 计算机科学

CS Algo Question

CS Algo Question# CS - 计算机科学

l*t2004-12-07 08:12

1 楼

1. Create a function findZeroArraySize() that takes a 2-dimensions int array
, its width and its height as arguments. The array is filled with 0 and 1. T
he function returns the size (in int) of the biggest 2-dimensions sub-array
filled only with 0. This function should be as fast as possible.
Ex:
If argument is , function returns 9.
001011110
110001100
010000011
110001100
111011100
Thanks a lot.

c*y2004-12-07 08:12

2 楼

return 3吧？

【在 l***t 的大作中提到】

: 1. Create a function findZeroArraySize() that takes a 2-dimensions int array
: , its width and its height as arguments. The array is filled with 0 and 1. T
: he function returns the size (in int) of the biggest 2-dimensions sub-array
: filled only with 0. This function should be as fast as possible.
: Ex:
: If argument is , function returns 9.
: 001011110
: 110001100
: 010000011
: 110001100

z*n2004-12-07 08:12

3 楼

I guess so.

【在 c********y 的大作中提到】

: return 3吧？

l*t2004-12-07 08:12

4 楼

No, it is 9.
the largest 0 sub matrix has 9 zeros :
000
000
000

【在 z*****n 的大作中提到】

: I guess so.

z*n2004-12-07 08:12

5 楼

hehe, got it.

【在 l***t 的大作中提到】

: No, it is 9.
: the largest 0 sub matrix has 9 zeros :
: 000
: 000
: 000

s*e2004-12-07 08:12

6 楼

I think I have an algorithm in mind. Suppose the size of the original matrix
is a * b. The complexity of my algorithm is O(ab). Not very fast ...

【在 l***t 的大作中提到】

a*t2004-12-07 08:12

7 楼

There are a*b elements in the matrix. You have to access each at least once.
If your algorithm is O(ab), it is pretty fast, I think.

【在 s******e 的大作中提到】

: I think I have an algorithm in mind. Suppose the size of the original matrix
: is a * b. The complexity of my algorithm is O(ab). Not very fast ...

g*a2004-12-07 08:12

8 楼

当年我们的算法作业题啊

【在 s******e 的大作中提到】

: I think I have an algorithm in mind. Suppose the size of the original matrix
: is a * b. The complexity of my algorithm is O(ab). Not very fast ...

m*h2004-12-07 08:12

9 楼

I think it can be solved by scanning the matrix column by column while
maintaning a measure, say, T(i), which is the maximum all 0 sub matirx before
scanning to column i, and then update T(i). The complexity should be
O(ab).

array
T
sub-array

【在 s******e 的大作中提到】

: I think I have an algorithm in mind. Suppose the size of the original matrix
: is a * b. The complexity of my algorithm is O(ab). Not very fast ...

a*t2004-12-07 08:12

10 楼

How can you gaurantee the solution in T(i) is the largest?
1111001111
1110000111
1100000011
1000000001
0000000000
1000000001
.......

【在 m****h 的大作中提到】

: I think it can be solved by scanning the matrix column by column while
: maintaning a measure, say, T(i), which is the maximum all 0 sub matirx before
: scanning to column i, and then update T(i). The complexity should be
: O(ab).
:
: array
: T
: sub-array

s*v2004-12-07 08:12

11 楼

O(n*n*n)

a*t2004-12-07 08:12

12 楼

Where did you find these problems? homework?
These problems are listed at
http://trikuare.cx/mt/archives/000718.php

【在 l***t 的大作中提到】

m*h2004-12-07 08:12

13 楼

It's like induction. It is simple when scanning the first column. Then, in the
folowing steps, we need only check the new column, to see if T(i) can be made
any larger.

before
matrix

【在 a******t 的大作中提到】

: Where did you find these problems? homework?
: These problems are listed at
: http://trikuare.cx/mt/archives/000718.php