2024-02-28:用go语言,有一个由x轴和y轴组成的坐标系,
"y下"和"y上"表示一条无限延伸的道路,"y下"表示这个道路的下限,"y上"表示这个道路的上限,
给定一批长方形,每一个长方形有(x1, x2, y1, y2),4个坐标可以表示一个长方形,
判断这条道路整体是不是可以走通的。
以下为正式题目:
图片在计算机处理中往往是使用二维矩阵来表示的,
给你一个大小为 m x n 的二进制矩阵 image 表示一张黑白图片,0 代表白色像素,1 代表黑色像素,
黑色像素相互连接,也就是说,图片中只会有一片连在一块儿的黑色像素。像素点是水平或竖直方向连接的。
给你两个整数 x 和 y 表示某一个黑色像素的位置。
请你找出包含全部黑色像素的最小矩形(与坐标轴对齐),并返回该矩形的面积。
你必须设计并实现一个时间复杂度低于 O(m*n) 的算法来解决此问题。
输入:image = [[“0”,“0”,“1”,“0”],[“0”,“1”,“1”,“0”],[“0”,“1”,“0”,“0”]], x = 0, y = 2。
输出:6。
答案2024-02-28:
来自左程云。
大体步骤如下:
1.定义一个辅助函数minArea(image [][]byte, x int, y int) int
,用于计算包含全部黑色像素的最小矩形的面积。
2.在minArea
函数中,使用二分查找来确定矩形的左边界、右边界、上边界和下边界。
3.实现辅助函数left(image [][]byte, col int) int
,用于确定左边界。采用二分查找方法,在给定的列col中向左查找,直到找到第一个出现黑色像素的位置。
4.实现辅助函数right(image [][]byte, col int) int
,用于确定右边界。采用二分查找方法,在给定的列col中向右查找,直到找到最后一个出现黑色像素的位置。
5.实现辅助函数up(image [][]byte, row int, left int, right int) int
,用于确定上边界。采用二分查找方法,在给定的行row中从左边界到右边界之间查找,直到找到第一个出现黑色像素的位置。
6.实现辅助函数down(image [][]byte, row int, left int, right int) int
,用于确定下边界。采用二分查找方法,在给定的行row中从左边界到右边界之间查找,直到找到最后一个出现黑色像素的位置。
7.在minArea
函数中,调用辅助函数获取左边界、右边界、上边界和下边界,并计算矩形的面积((right - left + 1) * (down - up + 1)
)。
8.在main
函数中,定义一个示例图片image
和给定的点(x, y)
,调用minArea
函数并将结果打印出来。
总的时间复杂度:由于每个辅助函数都采用了二分查找的方法,时间复杂度为O(logn),所以总的时间复杂度为O(logn)。
总的额外空间复杂度:除了存储输入数据和输出结果的额外空间外,代码没有使用其他额外的空间,因此总的额外空间复杂度为O(1)。
go完整代码如下:
package main
import "fmt"
func minArea(image [][]byte, x int, y int) int {
left := left(image, y)
right := right(image, y)
up := up(image, x, left, right)
down := down(image, x, left, right)
return (right - left + 1) * (down - up + 1)
}
func left(image [][]byte, col int) int {
l, r, m, ans := 0, col-1, 0, col
find := false
for l <= r {
m = (l + r) / 2
find = false
for i := 0; i < len(image); i++ {
if image[i][m] == '1' {
find = true
break
}
}
if find {
ans = m
r = m - 1
} else {
l = m + 1
}
}
return ans
}
func right(image [][]byte, col int) int {
l, r, m, ans := col+1, len(image[0])-1, 0, col
find := false
for l <= r {
m = (l + r) / 2
find = false
for i := 0; i < len(image); i++ {
if image[i][m] == '1' {
find = true
break
}
}
if find {
ans = m
l = m + 1
} else {
r = m - 1
}
}
return ans
}
func up(image [][]byte, row int, left int, right int) int {
u, d, m, ans := 0, row-1, 0, row
find := false
for u <= d {
m = (u + d) / 2
find = false
for i := left; i <= right; i++ {
if image[m][i] == '1' {
find = true
break
}
}
if find {
ans = m
d = m - 1
} else {
u = m + 1
}
}
return ans
}
func down(image [][]byte, row int, left int, right int) int {
u, d, m, ans := row+1, len(image)-1, 0, row
find := false
for u <= d {
m = (u + d) / 2
find = false
for i := left; i <= right; i++ {
if image[m][i] == '1' {
find = true
break
}
}
if find {
ans = m
u = m + 1
} else {
d = m - 1
}
}
return ans
}
func main() {
image := [][]byte{{'0', '0', '1', '0'}, {'0', '1', '1', '0'}, {'0', '1', '0', '0'}}
x := 0
y := 2
result := minArea(image, x, y)
fmt.Println(result)
}
python代码如下:
# -*-coding:utf-8-*-
def minArea(image, x, y):
left = left_boundary(image, y)
right = right_boundary(image, y)
up = upper_boundary(image, x, left, right)
down = lower_boundary(image, x, left, right)
return (right - left + 1) * (down - up + 1)
def left_boundary(image, col):
l, r, m, ans = 0, col-1, 0, col
find = False
while l <= r:
m = (l + r) // 2
find = False
for i in range(len(image)):
if image[i][m] == '1':
find = True
break
if find:
ans = m
r = m - 1
else:
l = m + 1
return ans
def right_boundary(image, col):
l, r, m, ans = col+1, len(image[0])-1, 0, col
find = False
while l <= r:
m = (l + r) // 2
find = False
for i in range(len(image)):
if image[i][m] == '1':
find = True
break
if find:
ans = m
l = m + 1
else:
r = m - 1
return ans
def upper_boundary(image, row, left, right):
u, d, m, ans = 0, row-1, 0, row
find = False
while u <= d:
m = (u + d) // 2
find = False
for i in range(left, right+1):
if image[m][i] == '1':
find = True
break
if find:
ans = m
d = m - 1
else:
u = m + 1
return ans
def lower_boundary(image, row, left, right):
u, d, m, ans = row+1, len(image)-1, 0, row
find = False
while u <= d:
m = (u + d) // 2
find = False
for i in range(left, right+1):
if image[m][i] == '1':
find = True
break
if find:
ans = m
u = m + 1
else:
d = m - 1
return ans
image = [['0', '0', '1', '0'], ['0', '1', '1', '0'], ['0', '1', '0', '0']]
x = 0
y = 2
result = minArea(image, x, y)
print(result)
标签:02,right,int,image,长方形,像素,道路,col,left
From: https://www.cnblogs.com/moonfdd/p/18041063