arrays - 二维数组，用指定值修剪

Question

用指定值修剪二维数组的好方法是什么？

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]

修剪操作应该能够从四个边中的任何一个切掉。

Answer 1

伪代码:

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++)中，for 循环应该更快，因为 locality of reference和 vectorization .