Uriel's Corner

Research Associate @ Harvard University / Research Interests: Computer Vision, Biomedical Image Analysis, Machine Learning
posts - 0, comments - 50, trackbacks - 0, articles - 594
给出一个二维数字矩阵,每行从左到右递增,下一行第一个数大于上一行最后一个数,问某个数字target是否在矩阵里

方法一:当成一个1D递增向量,二分,O(log(N*M))
Python实现
 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++实现
 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 };


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理