修剪具有指定值的二维数组的好方法是什么?
A = [0 0 0 0 0]
[1 2 3 0 0]
[4 0 6 0 0]
[0 0 0 0 0]
B = trim(A, 0)
// results in:
// B = [1 2 3]
// [4 0 6]
修剪操作应该能够从四个边中的任何一个切掉。
最佳答案
伪代码:
trim(array[WIDTH][HEIGHT], trimmed):
// top left corner will be (xmin, ymin)
xmin = WIDTH
ymin = HEIGHT
// bottom right corner will be (xmax, ymax)
xmax = -1
ymax = -1
for (y = 0; y < HEIGHT; y++):
for (x = 0; x < WIDTH; x++):
if (array[x][y] != trimmed):
if (xmin > x) xmin = x
if (xmax < x) xmax = x
if (ymin > y) ymin = y
if (ymax < y) ymax = y
if (xmin == WIDTH)
return an empty array
else
return sub-array with top left corner in (xmin, ymin)
and bottom right corner in (xmax, ymax)
时间复杂度是
O(WIDTH * HEIGHT)
,空间复杂度是 O(1)
。在某些编程语言(如 C 或 C++)中,由于 locality of reference 和 vectorization
for
循环应该快得多。关于arrays - 二维数组,用指定值修剪,我们在Stack Overflow上找到一个类似的问题:https://stackoverflow.com/questions/30697790/