2D数组，按指定值修剪 [英] 2d array, trim with specified value

问题描述

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

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屋！