首页 > 代码库 > Smallest Rectangle Enclosing Black Pixels
Smallest Rectangle Enclosing Black Pixels
Note: 约等于O(nlogn)
public class Solution { /** * @param image a binary matrix with ‘0‘ and ‘1‘ * @param x, y the location of one of the black pixels * @return an integer */ public int minArea(char[][] image, int x, int y) { // Write your code here if(image == null || image.length == 0) { return 0; } if (image[0] == null || image[0].length == 0) { return 0; } int nRow = image.length; int nCol = image[0].length; //find the right boarder int start = y; int end = nCol - 1; while (start + 1 < end) { int mid = start + (end - start) / 2; if (checkCol(image, mid)) { start = mid; } else { end = mid; } } int right = start; if (checkCol(image, end)) { right = end; } //find the left boarder start = 0; end = y; while (start + 1 < end) { int mid = start + (end - start) / 2; if (checkCol(image, mid)) { end = mid; } else { start = mid; } } int left = end; if (checkCol(image, start)) { left = start; } //find the up boarder start = 0; end = x; while (start + 1 < end) { int mid = start + (end - start) / 2; if (checkRow(image, mid)) { end = mid; } else { start = mid; } } int up = end; if (checkRow(image, start)) { up = start; } //find the down boarder start = x; end = nRow - 1; while (start + 1 < end) { int mid = start + (end - start) / 2; if (checkRow(image, mid)) { start = mid; } else { end = mid; } } int down = start; if (checkRow(image, end)) { down = end; } return (right - left + 1) * (down - up + 1); } private boolean checkCol(char[][] image, int col) { for (int i = 0; i < image.length; i++) { if (image[i][col] == ‘1‘) { return true; } } return false; } private boolean checkRow(char[][] image, int row) { for (int i = 0; i < image[row].length; i++) { if (image[row][i] == ‘1‘) { return true; } } return false; } }
Smallest Rectangle Enclosing Black Pixels
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。