# |
Title |
Difficulty |
Topic |
74 |
Search a 2D Matrix |
Medium |
Array; Binary Search |
Description
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.
Example 1:
1 2 3 4 5 6 7 8
|
Input: matrix = [ [1, 3, 5, 7], [10, 11, 16, 20], [23, 30, 34, 50] ] target = 3 Output: true
|
Example 2:
1 2 3 4 5 6 7 8
|
Input: matrix = [ [1, 3, 5, 7], [10, 11, 16, 20], [23, 30, 34, 50] ] target = 13 Output: false
|
Analyze
当作一个排序数组来做。
Submission
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17
|
class { public boolean searchMatrix(int[][] matrix, int target) { if(matrix == null || matrix.length == 0 || matrix[0] == null || matrix[0].length == 0) return false; int m = matrix.length, n = matrix[0].length; int lo = 0, hi = m * n - 1; while(lo < hi) { int mid = (lo + hi) / 2; if(matrix[mid / n][mid % n] < target) { lo = mid + 1; } else { hi = mid; } } return matrix[lo / n][lo % n] == target; } }
|
Complex Analyze
时间复杂度为$$O(log(m times n))$$。
近期评论