Search a 2D Matrix

Search a 2D Matrix II

Write an efficient algorithm that searches for a value in an m x n matrix, return the occurrence of it.

This matrix has the following properties:

Integers in each row are sorted from left to right.
Integers in each column are sorted from up to bottom.
No duplicate integers in each row or column.

Example

Consider the following matrix:

[

  [1, 3, 5, 7],

  [2, 4, 7, 8],

  [3, 5, 9, 10]

]

Given target = 3, return 2.

分析：

因为数组里的数有上面三个特性，所以我们可以从左下角开始找。如果当前值比target大，明显往上走，比target小，往右走，如果一样斜上走。Time complexity: (O(m + n)) (m = matrix.length, n = matrix[0].length)

 public class Solution {

     public int searchMatrix(int[][] matrix, int target) {

         // check corner case

         if (matrix == null || matrix.length == 0 || matrix[].length == 0) {

             return ;

         }

         // from bottom left to top right

         int x = matrix.length - ;

         int y = ;

         int count = ;

         while (x >=  && y < matrix[].length) {

             if (matrix[x][y] < target) {

                 y++;

             } else if (matrix[x][y] > target) {

                 x--;

             } else {

                 count++;

                 x--;

                 y++;

             }

         }

         return count;

     }

 }

Search a 2D Matrix I

Write an efficient algorithm that searches for a value in an mx 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

Consider the following matrix:

[

    [1, 3, 5, 7],

    [10, 11, 16, 20],

    [23, 30, 34, 50]

]

Given target = 3, return true.

分析：

根据数组的特点，我们需要找出一个大范围（row），然后再确定小范围。

 public class Solution {

     public boolean searchMatrix(int[][] matrix, int target) {

         if (matrix == null || matrix.length ==  || matrix[].length == ) return false;

         int rowCount = matrix.length, colCount = matrix[].length;

         if (matrix[][] > target || matrix[rowCount - ][colCount - ] < target) return false;

         int row = getRowNumber(matrix, target);

         int column = getColumnNumber(matrix, row, target);

         return matrix[row][column] == target;

     }

     public int getRowNumber(int[][] matrix, int target) {

         int start = , end = matrix.length - , width = matrix[].length;

         while (start <= end) {

             int mid = start + (end - start) / ;

             if (matrix[mid][width - ] == target) {

                 return mid;

             } else if (matrix[mid][width - ] > target) {

                 end = mid - ;

             } else {

                 start = mid + ;

             }

         }

         return start;

     }

     public int getColumnNumber(int[][] matrix, int row, int target) {

         int start = , end = matrix[].length;

         while (start <= end) {

             int mid = start + (end - start) / ;

             if (matrix[row][mid] == target) {

                 return mid;

             } else if (matrix[row][mid] > target) {

                 end = mid - ;

             } else {

                 start = mid + ;

             }

         }

         return start;

     }

 }

巴特西

Search a 2D Matrix | & II

Search a 2D Matrix II

Search a 2D Matrix I

最新文章

热门文章