首页 > 代码库 > leetcode 【Search a 2D Matrix 】python 实现
leetcode 【Search a 2D Matrix 】python 实现
题目：
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 from left to right.
- The first integer of each row is greater than the last integer of the previous row.
For example,
Consider the following matrix:
[ [1, 3, 5, 7], [10, 11, 16, 20], [23, 30, 34, 50]]
Given target = 3, return true.
代码：oj测试通过 Runtime: 75 ms
1 class Solution: 2 # @param matrix, a list of lists of integers 3 # @param target, an integer 4 # @return a boolean 5 def searchInline(self, line, target): 6 start = 0 7 end = len(line)-1 8 while start <= end : 9 if start == end :10 return [False,True][line[start]==target]11 if start+1 == end :12 if line[start]==target or line[end]==target :13 return True14 else:15 return False16 mid=(start+end)/217 if line[mid]==target :18 return True19 elif line[mid]>target :20 end = mid-121 else :22 start = mid+123 24 def searchMatrix(self, matrix, target):25 if len(matrix) == 0 :26 return False27 28 if len(matrix) == 1 :29 return self.searchInline(matrix[0], target)30 31 if len(matrix) == 2 :32 return self.searchInline([matrix[1],matrix[0]][matrix[1][0]>target], target)33 34 start = 035 end = len(matrix)-136 while start <= end :37 if start == end:38 return self.searchInline(matrix[start],target)39 if start+1 == end:40 if matrix[start][0] <= target and matrix[end][0] > target:41 return self.searchInline(matrix[start],target)42 if matrix[end][0] < target :43 return self.searchInline(matrix[end],target)44 mid = (start+end+1)/245 if matrix[mid][0] <= target and matrix[mid+1][0] > target:46 return self.searchInline(matrix[mid],target)47 elif matrix[mid][0] > target :48 end = mid-149 else :50 start = mid+1
思路：
先按行二分查找，再按列二分查找。
代码写的比较繁琐。
leetcode 【Search a 2D Matrix 】python 实现
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。