Title: Search a 2D Matrix II Source: leetcode.com
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 2 3 4 5 6 7 |
[ [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.
Java solution
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 |
/* https://leetcode.com/problems/search-a-2d-matrix-ii/ */ public class SearchA2DMatrixII { public static void main(String args[]) { SearchA2DMatrixII s = new SearchA2DMatrixII(); int[][] 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} }; System.out.println(s.searchMatrix(matrix, 25)); } public boolean searchMatrix(int[][] matrix, int target) { int row = 0; int col = matrix[0].length-1; while(row<matrix.length && col>-1) { if(matrix[row][col]==target) return true; else if(matrix[row][col] > target) col--; else if(matrix[row][col] < target) row++; } return false; } } |