概念

  • 对于一个sorted array, 一共有首尾两个指针,每次都是取中间的数。拿中间的数去跟target number进行比较。所以每次可以去掉一般的数字
  • 时间复杂度为O(logn)
  • 递归(Recursion)和while loop都可以实现二分,工程中尽量避免递归,可能会引起stackoverflow

二分法key points

  • while循环条件: start + 1 < end (start+1=end为相邻情况,那么终止只可能是相邻或者相交,因为开始给的竖直就已经有可能有相邻或者相交的情况出现,这样进一步加了排查情况。最后就需要处理一下,start为target还是end为target)(比如数组只有1, 2两个数的时候,如果start<end为循环条件,mid=(start+end)/2就会造成死循环)

  • mid定义: start + (end-start)/2

  • 在我们的loop中:判断A[mid] == 是否等于我们需要的结果,否则如果小于的话要怎么移动光标,如果大于的话要怎么移动光标

  • 最后已经跳出loop之后,判断A[start], A[end]是否为我们需要的结果

Smallest Rectangle Enclosing Black Pixels

1
2
3
4
5
6
7
8
9
10
11
An image is represented by a binary matrix with 0 as a white pixel and 1 as a black pixel. The black pixels are connected, i.e., there is only one black region. Pixels are connected horizontally and vertically. Given the location (x, y) of one of the black pixels, return the area of the smallest (axis-aligned) rectangle that encloses all black pixels.

For example, given the following image:

[
"0010",
"0110",
"0100"
]
and x = 0, y = 2,
Return 6.

这个题一开始一直想不通为什么会用二分法来解。看了下网上的答案之后发现这个思路还挺难考虑的。主要的点在于如果要找他的边界的话,那么从当前给的x, y这个点分别向他的上下左右二分。
但是并不是说直接找1, 而是找所在的行/列是否有1映射。也就是说定义一个方法来判断当前二分到的这个mid,是不是有1的映射,这样相当于又通过any 或者是 in 来判断一次。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
class Solution(object):
# @param image {List[List[str]]} a binary matrix with '0' and '1'
# @param x, y {int} the location of one of the black pixels
# @return an integer
def minArea(self, image, x, y):
# Write your code here
if not image:
return -1
n_row = len(image)
if n_row == 0:
return -1
n_col = len(image[0])
if n_col == 0:
return -1

top = self.searchRow(image, 0, x, True)
bottom = self.searchRow(image, x+1, n_row, False)
left = self.searchCol(image, 0, y, top, bottom, True)
right = self.searchCol(image, y+1,n_col, top, bottom, False)
return (bottom - top) * (right - left)

def searchRow(self, image, l, r, first_black):
while(l < r):
mid = (l + r)/2
is_black = self.is_black_row(image, mid) # mid这一行有黑快
if is_black == first_black:
r = mid
else:
l = mid + 1
return r

def is_black_row(self, image, yid):
# 某一行有黑块
return '1' in image[yid]

def is_black_col(self,image, xid, l, r):
return any(image[k][xid] == '1' for k in range(l, r))

def searchCol(self, image, l, r, u, d, first_black):
while(l< r):
mid = (l + r)/2
if self.is_black_col(image, mid, u, d) == first_black:
r = mid
else:
l = mid + 1
return r