LintCode: Search A 2d Matrix

简介:

1.

设查找的数位y,第一行最后一列的数位x

如果x<y,x是第一行最大的,所以第一行都小于y,删除第一行;

如果x>y,x是最后一列最小的,所以最后一列都大于y,删除最后一列;

这样保证x永远在可能有解的矩阵的第一行,最后一列。

时间复杂度:O(m+n)

复制代码
 1 class Solution {
 2 public:
 3     /**
 4      * @param matrix, a list of lists of integers
 5      * @param target, an integer
 6      * @return a boolean, indicate whether matrix contains target
 7      */
 8     bool searchMatrix(vector<vector<int> > &matrix, int target) {
 9         // write your code here
10         int m = matrix.size();
11         if (m == 0) {
12             return false;
13         }
14         int n = matrix[0].size();
15         int r = 0, c = n - 1;
16         while (r < m && c >= 0) {
17             if (matrix[r][c] < target) {
18                 r++;
19             } else if (matrix[r][c] > target) {
20                 c--;
21             } else {
22                 return true;
23             }
24         }
25         return false;
26     }
27 };
复制代码

 

2. 分治法1

设查找的数位y,取中心点x,把矩阵分解成4部分

如果x<y,x是A中最大的,所以A都小于y,删除A;

如果x>y,x是D中最小的,所以D都小于y,删除D;

A  | B

————

C  | D

时间复杂度:O(N) = O(N/4)+O(N/2)+O(1), 介于O(N^0.5)~O(N)之间

复制代码
 1 class Solution {
 2 public:
 3     /**
 4      * @param matrix, a list of lists of integers
 5      * @param target, an integer
 6      * @return a boolean, indicate whether matrix contains target
 7      */
 8     bool helper(vector<vector<int> > &M, int x1, int y1, int x2, int y2, int target) {
 9         if (x1 > x2 || y1 > y2) {//empty matrix
10             return false;
11         }
12         int midx = (x1 + x2)>>1;
13         int midy = (y1 + y2)>>1;
14         if (M[midx][midy] == target) {
15             return true;
16         }
17         return (M[midx][midy] > target)?
18         (helper(M, x1, y1, x2, midy-1, target)||helper(M, x1, midy, midx-1, y2, target)):
19         (helper(M, x1, midy+1, x2, y2, target)||helper(M, midx+1, y1, x2, midy, target));
20         
21     }
22     bool searchMatrix(vector<vector<int> > &matrix, int target) {
23         // write your code here
24         int m = matrix.size();
25         if (m == 0) {
26             return false;
27         }
28         int n = matrix[0].size();
29         return helper(matrix, 0, 0, m - 1, n - 1, target);
30     }
31 };
复制代码

 

3. 分治法2 

设查找的数为y,在中线找到这样两个数x1,x2,使得x1<y,x2>y,把矩阵分成4部分

A|     B

————

C|    D

x1是A中最大的,所以A都小于y,删掉A;

x2是D中最小的,所以D都大于y,删掉D;

时间复杂度:O(N)=2O(N/4)+O(logn), 为O(N^0.5) 

复制代码
 1 class Solution {
 2 public:
 3     /**
 4      * @param A, a list of integers
 5      * @param left, an integer
 6      * @param right, an integer
 7      * @param target, an integer
 8      * @return an integer, indicate the index of the last number less than or equal to target in A
 9      */
10     int binarySearch(vector<int> &A, int left, int right, int target) {
11         while (left <= right) {//not an empty list
12             int mid = (left + right) >> 1;
13             if (A[mid] <= target) {
14                 left = mid + 1;//left is in the integer after the last integer less than or equal to target 
15             } else {
16                 right = mid - 1;
17             }
18         }
19         return left - 1;
20     }
21     /**
22      * @param M, a list of lists of integers
23      * @param x1, an integer
24      * @param y1, an integer
25      * @param x2, an integer
26      * @param y2, an integer
27      * @param target, an integer
28      * @return a boolean, indicate whether matrix contains target
29      */
30     bool helper(vector<vector<int> > &M, int x1, int y1, int x2, int y2, int target) {
31         if (x1 > x2 || y1 > y2) {//empty matrix
32             return false;
33         }
34         int midx = (x1 + x2)>>1;
35         int indy = binarySearch(M[midx], y1, y2, target);
36         //M[midx][indy] <= target
37         if ((indy >= y1) && (M[midx][indy] == target)) {
38             return true;
39         }
40         return (helper(M, x1, indy+1, midx-1, y2, target))||(helper(M, midx+1, y1, x2, indy, target));
41         
42     }
43     /**
44      * @param matrix, a list of lists of integers
45      * @param target, an integer
46      * @return a boolean, indicate whether matrix contains target
47      */
48     bool searchMatrix(vector<vector<int> > &matrix, int target) {
49         // write your code here
50         int m = matrix.size();
51         if (m == 0) {
52             return false;
53         }
54         int n = matrix[0].size();
55         return helper(matrix, 0, 0, m - 1, n - 1, target);
56     }
57 };
复制代码

 



相关文章
Leetcode 74. Search a 2D Matrix
这道题很简单,为此专门写篇博客其实算博客凑数了。给你一个每一行每一列都是增序,且每一行第一个数都大于上一行末尾数的矩阵,让你判断某个数在这个矩阵中是否存在。 假设矩阵是m*n,扫一遍的时间复杂度就是O(m*n),题目中给出的这么特殊的矩阵,时间复杂度可以降到O(m+n),具体代码如下,写的比较挫。
83 1
Leetcode 240. Search a 2D Matrix II
具体思路就是每一行倒着扫,扫到第一个比target小的数就跳到下行,如果等于当然是直接返回true了,如果下一行还比target小就继续跳下一行,直到最后一行。 为啥这么做是可行的? 可能我比较笨,想了半天才想到。 因为每一列都是增序的,举个例子,假设matrix[0][5] > target,那么[0][5]位置右下(包含右和下)所有元素不可能比target小。
44 0
|
算法
LeetCode 74. Search a 2D Matrix
编写一个有效的算法,搜索m×n矩阵中的值。 此矩阵具有以下属性: 每行中的整数从左到右排序. 每行的第一个整数大于前一行的最后一个整数.
77 0
LeetCode 74. Search a 2D Matrix
|
算法
LeetCode 240. Search a 2D Matrix II
编写一个高效的算法来搜索 m x n 矩阵 matrix 中的一个目标值 target。该矩阵具有以下特性: 每行的元素从左到右升序排列。 每列的元素从上到下升序排列。
79 0
LeetCode 240. Search a 2D Matrix II
|
人工智能 C++ 索引
[LeetCode]--74. Search a 2D Matrix
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
1166 0
LeetCode - 34. Search for a Range
34. Search for a Range  Problem's Link  ---------------------------------------------------------------------------- Mean:  给定一个有序数组和一个数k,求k在这个数组中的起始下标和结束下标.
894 0
[LeetCode] Search a 2D Matrix
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
1215 0