首页 > 代码库 > [Leetcode] Binary search, Divide and conquer--240. Search a 2D Matrix II
[Leetcode] Binary search, Divide and conquer--240. Search a 2D Matrix II
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.
For 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.
Solution:
1. 1st idea use one binary search
iterate every rows , binary search from row i to find the insertion position p (bisect_right)
m = len(matrix), n = len(matrix[0]) time complexity O(m*logn)
1 if len(matrix) == 0 or len(matrix[0]) == 0: 2 return False 3 i = 0 4 while (i < len(matrix)): 5 pos = bisect_right(matrix[i], target) #use binary search 6 #print(" aaas: ",i, pos-1) 7 if matrix[i][pos-1] == target: 8 return True 9 i += 1 10 return False
2. 2nd utilize the ordered row and column, start from bottom left value v, if v is bigger than target, then go the upper column, else go the right row. time complexity o(m+n)
1 if len(matrix) == 0 or len(matrix[0]) == 0: 2 return False 3 m = len(matrix) 4 n = len(matrix[0]) 5 i = m-1 #row 6 j = 0 #column 7 while ( i >= 0 and j <= n-1): 8 if matrix[i][j] == target: 9 return True 10 elif matrix[i][j] > target: 11 i -= 1 12 else: 13 j += 1 14 return False
3. we can also use divide and conquer:
reference:
http://www.geeksforgeeks.org/divide-conquer-set-6-search-row-wise-column-wise-sorted-2d-array/
[Leetcode] Binary search, Divide and conquer--240. Search a 2D Matrix II
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。