2D数组,按指定值修剪 [英] 2d array, trim with specified value
本文介绍了2D数组,按指定值修剪的处理方法,对大家解决问题具有一定的参考价值,需要的朋友们下面随着小编来一起学习吧!
问题描述
修剪具有指定值的二维数组的好方法是什么?
What's a good way to trim a 2d array with a specified value?
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]
修剪操作应该能够从四个侧面中的任何一个切掉。
The trim operation should be able to cut away from any of the four sides.
推荐答案
伪代码:
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(宽度*高度)
,空间复杂度为 O(1)
。
Time complexity is O(WIDTH * HEIGHT)
, space complexity is O(1)
.
在某些编程语言(例如C或C ++)中,由于 for 循环应该快得多
In some programming languages (like C or C++) that for
loop should be much faster due to locality of reference and vectorization.
这篇关于2D数组,按指定值修剪的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!
查看全文