給出一個(gè)二維數(shù)字矩陣，每行從左到右遞增，下一行第一個(gè)數(shù)大于上一行最后一個(gè)數(shù)，問(wèn)某個(gè)數(shù)字target是否在矩陣?yán)?br />
方法一：當(dāng)成一個(gè)1D遞增向量，二分，O(log(N*M))
Python實(shí)現(xiàn)
1 #74
2 #Runtime: 19 ms (Beats 97.2%)
3 #Memory: 13.6 MB (Beats 95.32%)
4
5 class Solution(object):
6 def searchMatrix(self, matrix, target):
7 """
8 :type matrix: List[List[int]]
9 :type target: int
10 :rtype: bool
11 """
12 l, r = 0, len(matrix[0]) * len(matrix) - 1
13 while l < r:
14 mid = (l + r) // 2
15 if matrix[mid // len(matrix[0])][mid % len(matrix[0])] < target:
16 l = mid + 1
17 else:
18 r = mid
19 return matrix[l // len(matrix[0])][l % len(matrix[0])] == target
方法二：先確定在哪一行，再掃描該行所有列，O(N+M)
C++實(shí)現(xiàn)
1 //74
2 //Runtime: 56 ms (Beats 16.15%)
3
4 class Solution {
5 public:
6 bool searchMatrix(vector<vector<int> > &matrix, int target) {
7 int n = matrix.size();
8 int m = matrix[0].size();
9 int i, j;
10 for(i = 0; i < n; ++i) {
11 if(matrix[i][0] > target) {
12 --i;
13 break;
14 }
15 if(i == n - 1) break;
16 }
17 if(i < 0) return false;
18 for(j = 0; j < m; ++j) {
19 if(matrix[i][j] == target) return true;
20 }
21 return false;
22 }
23 };