【Leetcode 热题 100】74. 搜索二维矩阵

题目背景

给你一个满足下述两条属性的                                    m                         ×                         n                              m \times n                  m×n 整数矩阵：

• 每行中的整数从左到右按非严酷递增次序分列。
  
• 每行的第一个整数大于前一行的末了一个整数。
  给你一个整数                                         t                            a                            r                            g                            e                            t                                  target                     target，假如                                         t                            a                            r                            g                            e                            t                                  target                     target 在矩阵中，返回                                         t                            r                            u                            e                                  true                     true；否则，返回                                         f                            a                            l                            s                            e                                  false                     false。
  

数据约束

•                                         m                            =                            m                            a                            t                            r                            i                            x                            .                            l                            e                            n                            g                            t                            h                                  m = matrix.length                     m=matrix.length
  
•                                         n                            =                            m                            a                            t                            r                            i                            x                            [                            i                            ]                            .                            l                            e                            n                            g                            t                            h                                  n = matrix.length                     n=matrix.length
  
•                                         1                            ≤                            m                            ,                            n                            ≤                            100                                  1 \le m, n \le 100                     1≤m,n≤100
  
•                                         −                            1                                       0                               4                                      ≤                            m                            a                            t                            r                            i                            x                            [                            i                            ]                            [                            j                            ]                            ,                            t                            a                            r                            g                            e                            t                            ≤                            1                                       0                               4                                            -10 ^ 4 \le matrix[j], target \le 10 ^ 4                     −104≤matrix[j],target≤104
  

解题过程

题目保证整个矩阵中的元素从上到下从左到右依次递增，也就是可以展开成一个递增的一维数组，可以用下标映射的方式，在这个假造的一维矩阵中举行二分搜索，时间复杂度为                                    O                         (                         l                         o                         g                         (                         m                         n                         )                         )                              O(log(mn))                  O(log(mn))。
还可以用排除法，参考 搜索二维矩阵 II。从矩阵的右上角开始，每次比较可以或许去掉一行或一列，相当于查找抽象的二叉搜索树，时间复杂度大致在                                    O                         (                         m                         +                         n                         )                              O(m + n)                  O(m+n) 这个量级。
详细实现
整体二分

1. class Solution {
2.     public boolean searchMatrix(int[][] matrix, int target) {
3.         int m = matrix.length, n = matrix[0].length;
4.         int left = 0, right = m * n;
5.         while(left < right) {
6.             int mid = left + ((right - left) >>> 1);
7.             int cur = matrix[mid / n][mid % n];
8.             if(cur == target) {
9.                 return true;
10.             }
11.             if(cur < target) {
12.                 left = mid + 1;
13.             } else {
14.                 right = mid;
15.             }
16.         }
17.         return false;
18.     }
19. }

复制代码

查找抽象二叉搜索树

1. class Solution {
2.     public boolean searchMatrix(int[][] matrix, int target) {
3.         int i = 0;
4.         int j = matrix[0].length - 1;
5.         while(i < matrix.length && j >= 0) {
6.             int cur = matrix[i][j];
7.             if(cur == target) {
8.                 return true;
9.             }
10.             if(cur < target) {
11.                 i++;
12.             } else {
13.                 j--;
14.             }
15.         }
16.         return false;
17.     }
18. }

复制代码

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。