-
Notifications
You must be signed in to change notification settings - Fork 423
/
Search2DMatrixII.py
174 lines (127 loc) · 4.53 KB
/
Search2DMatrixII.py
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
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
"""
Write an efficient algorithm that searches for a value in an m x n matrix. This matrix has the following properties:
Integers in each row are sorted in ascending from left to right.
Integers in each column are sorted in ascending from top to bottom.
Example:
Consider the following matrix:
[
[1, 4, 7, 11, 15],
[2, 5, 8, 12, 19],
[3, 6, 9, 16, 22],
[10, 13, 14, 17, 24],
[18, 21, 23, 26, 30]
]
Given target = 5, return true.
Given target = 20, return false.
思路：
已知条件：
每一行以及每一列都是升序排列的。
左上角是整个里面最小的。
右下角是整个里面最大的。
右上角是整行中最大的，但是是整列中最小的。
左下角是整列里最大的，整行里最小的。
1. 直接遍历，O(klogn)，每一行都用二分法，有些无脑，但有效。
passed，不过效率低，只beat了 7% 左右。
2. 基于上面的分析，应该是可以减少一些不必要的搜索的。
左下角是整列里最大的，如果target小于它则不必搜索这一整行，用二分法搜索这一列。
然后脱去这层
[
[1, 4, 7, 11, 15],
[2, 5, 8, 12, 19],
[3, 6, 9, 16, 22],
[10, 13, 14, 17, 24],
[18, 21, 23, 26, 30]
]
此时同样的思路搜索13，若target大于则不必搜索这一列，直接搜这一行即可。
[
[1, 4, 7, 11, 15],
[2, 5, 8, 12, 19],
[3, 6, 9, 16, 22],
[10, 13, 14, 17, 24],
[18, 21, 23, 26, 30]
]
直到搜索到右上角。
这样的效率也是 O(nlogn).
不出所料，比上个稍微好了那么一点点....
3. 基于上面的分析：
可以不用搜索，直接点对点。
搜了18，这个点，如果target比它大，那么就在这一行继续走，走到21，如果比它大那就继续在这一行走，到了23，
如果比它小就搜这一列，这样搜到row或column的尽头，有就是有，没有就是没有。
效率最差是 O(m+n)。
Good, beat 82%.
测试用例：
https://leetcode.com/problems/search-a-2d-matrix-ii/description/
"""
class Solution(object):
def binarySearch2(self, rawList, target):
split = len(rawList) // 2
left = rawList[:split]
right = rawList[split:]
if not left and not right:
return False
if left and left[-1] == target:
return True
if right and right[0] == target:
return True
if len(left) > 1 and left[-1] > target:
return self.binarySearch2(left, target)
if len(right) > 1 and right[0] < target:
return self.binarySearch2(right, target)
return False
def searchMatrix(self, matrix, target):
if not any(matrix):
return False
# column + row -
column, row = 0, len(matrix) - 1
column_length = len(matrix[0])
while row >= 0 and column < column_length:
if matrix[row][column] == target:
return True
if matrix[row][column] > target:
row -= 1
else:
column += 1
return False
# def searchMatrix(self, matrix, target):
# """
# :type matrix: List[List[int]]
# :type target: int
# :rtype: bool
# """
# if not any(matrix):
# return False
# # column + row -
# column, row = 0, len(matrix) - 1
# column_length = len(matrix[0])
# while row >= 0 and column < column_length:
# """
# left bottom to right top.
# """
# if matrix[row][column] == target:
# return True
# # search column.
# if matrix[row][column] > target:
# if self.binarySearch2([i[column] for i in matrix[:row]], target):
# return True
# # search row.
# else:
# if self.binarySearch2(matrix[row][column+1:], target):
# return True
# row -= 1
# column += 1
# return False
# def searchMatrix(self, matrix, target):
# """
# :type matrix: List[List[int]]
# :type target: int
# :rtype: bool
# """
# if not any(matrix):
# return False
# for i in matrix:
# if i[0] == target:
# return True
# if i[0] < target:
# if self.binarySearch2(i, target):
# return True
# return False