6 最小覆盖矩形(Smallest Rectangle Enclosing Black Pixels)

1 题目

??最小覆盖矩形(Smallest Rectangle Enclosing Black Pixels)

lintcode:题号——600,难度——hard

2 描述

??一个由二进制矩阵表示的图,0 表示白色像素点,1 表示黑色像素点。黑色像素点是联通的,即只有一块黑色区域。像素是水平和竖直连接的,给一个黑色像素点的坐标 (x, y) ,返回囊括所有黑色像素点的矩阵的最小面积。

??样例1:

输入:["0010","0110","0100"],x=0,y=2
输出:6
解释:

矩阵左上角坐标是(0, 1), 右下角的坐标是(2, 2)

??样例2:

输入:["1110","1100","0000","0000"], x = 0, y = 1
输出:6
解释:

矩阵左上角坐标是(0, 0), 右下角坐标是(1, 3)

3 思路

??从答案反向找思路,要得到面积,需要横向跨度和纵向跨度,横向需要分别找到最左边和最右边,纵向需要分别找到最上面和最下面,题中给出了一个种子点,即其中一个黑子所在的位置,从种子点分别向上、下、左、右四个方向看,例如向左的情况,需要找到最左端的黑子,而最左端的黑子不一定与种子点在同一行,所以我们要考虑整个左半矩阵图,由于只要找到最左端的横向坐标即可,不用关心列坐标,可以将左半矩阵图纵向压缩进同一行,这样只要该列存在任何黑子,则将压缩后形成的点标记为黑,因为所有的黑子是联通的,最后向左看的情况一定会形成“oooxxx”形式的数列,使用二分法即可找到最左端边缘。
??按照相同的思路可以找到其他三个方向的边缘,然后得到横纵跨度,再得到面积。

  1. 考虑左半矩阵,以每列是否存在黑子为条件,二分查找最左边缘;
  2. 分别得到四个方向的边缘;
  3. 计算横纵跨度,得到面积。

??扩展。

其实题目中给出的种子点有点奇怪,按照常理来判断给不给这个种子点的位置,都是能得到答案的,题中直接给出了,简化了这一步。题目也可以使用广度优先搜索来做,可以思考一下。

3.1 图解

输入:["0000100","0111100","0001100","0011110","0000000"],
x = 2, y = 4
输出:20

graph TD X[0表示白子,1和X表示黑子,X为种子点<br/>‘0, 0, 0, 0, 1, 0, 0‘<br/>‘0, 1, 1, 1, 1, 0, 0‘<br/>‘0, 0, 0, 1, X, 0, 0‘<br/>‘0, 0, 1, 1, 1, 1, 0‘<br/>‘0, 0, 0, 0, 0, 0, 0‘] X -- 左半矩阵 --> A[‘0, 0, 0, 0, 1‘<br/>‘0, 1, 1, 1, 1‘<br/>‘0, 0, 0, 1, X‘<br/>‘0, 0, 1, 1, 1‘<br/>‘0, 0, 0, 0, 0‘] X -- 上半矩阵 --> B[‘0, 0, 0, 0, 1, 0, 0‘<br/>‘0, 1, 1, 1, 1, 0, 0‘<br/>‘0, 0, 0, 1, X, 0, 0‘] X -- 右半矩阵 --> C[‘1, 0, 0‘<br/>‘1, 0, 0‘<br/>‘X, 0, 0‘<br/>‘1, 1, 0‘<br/>‘0, 0, 0‘] X -- 下半矩阵 --> D[‘0, 0, 0, 1, X, 0, 0‘<br/>‘0, 0, 1, 1, 1, 1, 0‘<br/>‘0, 0, 0, 0, 0, 0, 0‘] A --> A0[列中出现一个黑子1,则压缩后的点为1] A0 -- 分列 --> A1[0<br/>0<br/>0<br/>0<br/>0] A0 -- 分列 --> A2[0<br/>1<br/>0<br/>0<br/>0] A0 -- 分列 --> A3[0<br/>1<br/>0<br/>1<br/>0] A0 -- 分列 --> A4[0<br/>1<br/>1<br/>1<br/>0] A0 -- 分列 --> A5[1<br/>1<br/>X<br/>1<br/>0] A1 -- 压缩 --> A11[0] A2 -- 压缩 --> A21[1] A3 -- 压缩 --> A31[1] A4 -- 压缩 --> A41[1] A5 -- 压缩 --> A51[1] A11 --> AA[‘0, 1, 1, 1, 1‘] A21 --> AA A31 --> AA A41 --> AA A51 --> AA AA -- 二分查找得到左边缘<br/>下标都是指在整体矩阵中的下标 --> AAA[下标1] B -- 分行,压缩 --> BB[‘1‘<br/>‘1‘<br/>‘1‘] BB -- 上边缘 --> BBB[下标0] C -- 分列,压缩 --> CC[‘1, 1, 0‘] CC -- 右边缘 --> CCC[下标5] D -- 分行,压缩 --> DD[‘1‘<br/>‘1‘<br/>‘0‘] DD -- 下边缘 --> DDD[下标3] AAA --> AC[跨度5] CCC --> AC BBB --> BD[跨度4] DDD --> BD AC --> R[面积20] BD --> R

3.2 时间复杂度

??算法在每一个方向使用一次二分法,假定矩阵图有m行n列,相同维度的二分法耗时可以整体来算,横向上二分法操作的时间复杂度为O(log n),纵向上二分法操作的时间复杂度为O(log m)
??横向的二分法每次判断都包含一次对列的遍历操作的时间复杂度O(m),纵向的二分法每次判断都包含一次对行的遍历的时间复杂度O(m)
??横向二分法总耗时O(m * log n),纵向二分法总耗时O(n * log m)
??算法的时间复杂度为O(m * log n + n * log m),其中m为矩阵图的行数,n为矩阵图的列数。

3.3 空间复杂度

??算法的空间复杂度为O(1)

4 源码

??注意事项:

  1. 题目给出的种子点坐标(x, y),x表示二维数组的行序号,y表示二维数组的列序号,所以x是纵向的距离,y是横向的距离,这点和直角坐标系的x方向和y方向刚好相反,很容易想歪,思路要清晰;
  2. 求面积的时候,注意一个点代表一距离,不是一条边代表一距离。

??C++版本:

/**
 * @param image: 代表包含‘0‘和‘1‘为元素的二进制矩阵图
 * @param x: 初始黑点的纵坐标
 * @param y: 初始黑点的横坐标
 * @return: 最小覆盖矩形的面积
 */
int minArea(vector<vector<char>> &image, int x, int y) {
    // write your code here
    if (image.empty() || image.front().empty()) // 横纵都不能为空
    {
        return 0;
    }

    int maxRow = image.size() - 1;
    int maxColumn = image.front().size() - 1;

    // 计算四个方向最边缘点的下标
    int left = calLeftEdge(image, 0, y);
    int right = calRightEdge(image, y, maxColumn);
    int top = calTopEdge(image, 0, x);
    int bottom = calBottomEdge(image, x, maxRow);

    return (right - left + 1 ) * (bottom - top + 1);
}

// 计算最左边缘黑点的横坐标
int calLeftEdge(vector<vector<char>> & image, int start, int end)
{
    int mid = 0;
    while (start + 1 < end)
    {
        mid = start + (end - start) / 2;
        if (isColWhite(image, mid))
        {
            start = mid;
        }
        else
        {
            end = mid;
        }
    }

    if (isColWhite(image, start))
    {
        return end;
    }
    else
    {
        return start;
    }
}

// 计算最右边缘黑点的横坐标
int calRightEdge(vector<vector<char>> & image, int start, int end)
{
    int mid = 0;
    while (start + 1 < end)
    {
        mid = start + (end - start) / 2;
        if (isColWhite(image, mid))
        {
            end = mid;
        }
        else
        {
            start = mid;
        }
    }

    if (isColWhite(image, end))
    {
        return start;
    }
    else
    {
        return end;
    }
}

// 计算最上边缘黑点的纵坐标
int calTopEdge(vector<vector<char>> & image, int start, int end)
{
    int mid = 0;
    while (start + 1 < end)
    {
        mid = start + (end - start) / 2;
        if (isRowWhite(image, mid))
        {
            start = mid;
        }
        else
        {
            end = mid;
        }
    }

    if (isRowWhite(image, start))
    {
        return end;
    }
    else
    {
        return start;
    }
}

// 计算最下边缘黑点的纵坐标
int calBottomEdge(vector<vector<char>> & image, int start, int end)
{
    int mid = 0;
    while (start + 1 < end)
    {
        mid = start + (end - start) / 2;
        if (isRowWhite(image, mid))
        {
            end = mid;
        }
        else
        {
            start = mid;
        }
    }

    if (isRowWhite(image, end))
    {
        return start;
    }
    else
    {
        return end;
    }
}

// 判断行中是否全为白点
bool isRowWhite(vector<vector<char>> & image, int row)
{
    for (int i = 0; i < image.front().size(); i++)
    {
        if (image.at(row).at(i) == ‘1‘)
        {
            return false;
        }
    }

    return true;
}

// 判断列中是否全为白点
bool isColWhite(vector<vector<char>> & image, int col)
{
    for (int i = 0; i < image.size(); i++)
    {
        if (image.at(i).at(col) == ‘1‘)
        {
            return false;
        }
    }

    return true;
}

6 最小覆盖矩形(Smallest Rectangle Enclosing Black Pixels)

上一篇:docker-compose 高可用无法HOST解析导致无法连接


下一篇:C#中的委托和事件(续)