修剪具有指定值的二维数组的好方法是什么?

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 referencevectorization for 循环应该快得多。

关于arrays - 二维数组,用指定值修剪,我们在Stack Overflow上找到一个类似的问题:https://stackoverflow.com/questions/30697790/

10-12 07:40
查看更多