LeetCode-240-搜索二维矩阵II
题目
编写一个高效的算法来搜索 m x n 矩阵 matrix 中的一个目标值 target。该矩阵具有以下特性：
每行的元素从左到右升序排列。
每列的元素从上到下升序排列。
示例:
现有矩阵 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]
]
给定 target = 5，返回 true。
给定 target = 20，返回 false。
思路
很显然的思路就是暴力搜索，搜到target就退出，不过这样做很显然会超时，也不符合刷题的初衷；
思考其他思路，看到矩阵是经过了排序的，那么很自然的想到了二分法；
经过思考可以发现对于一维的数组来说，二分法很容易，但是对于矩阵来说，二分法就比较复杂；
首先是划分区域，对于一个一维数组，经过二分后会有两个区域，但是对于矩阵而言，二分后会有四个区域；
假如target为7，中间的数字为5的时候，
一维数组为：
[1,2,3,4,5,6,7,8,9] —-> [1,2,3,4]; [6,7,8,9];
由7>5可知从第二段数组中开始搜索；
但是对于矩阵而言，二分后会有四个区域，例如:
[1, 4, 7], (1): [1, 4] (2): [4, 7], (3):[2, 5], (4):[5, 8],
[2, 5, 8], [2, 5] [5, 8], [3, 6], [6, 9]
[3, 6, 9]
这时候要搜索7，只能排除矩阵1，其他几个矩阵均有可能包含数字7；
还有一个麻烦的地方，就是矩阵不一定是行列式，也就是说m*n的矩阵中，m不一定等于n；
这样的结果就是当二分到最小的时候会出现三种情况：
m>n时，搜索到的最小矩阵为2*1；
m<n时，搜索到的最小矩阵为1*2；
m=n时，搜索到的最小矩阵为1*1；
对于这种情况我也没有很好的处理方法，只能对三种情况分开处理，具体见代码；
最后的结果，效率不是很高，应该是对四个区域做剪枝的时候还有更好的办法排除其他区域，等有空的时候在想想吧。
代码
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
bool binarySearch(vector<vector<int>>& matrix, int target, int x1, int y1, int x2, int y2){
// 获取子矩阵左上角head，右下角tail
int head = matrix[x1][y1], tail = matrix[x2][y2];
//cout<<"search:"<<head<<","<<tail<<endl;
// 碰到了target直接返回
if (target == head || target == tail)
return true;
// 小于head或大于tail,则target肯定不在此子矩阵
if (target < head || target > tail)
return false;
// 搜索到1*2 2*1 1*1矩阵，分类判断
if (x2-x1 == 1 && y2-y1 ==0)
return false;
if (x2-x1==0 && y2-y1==1)
return false;
if (x2-x1 == 1 && y2-y1==1)
{
if (matrix[x1+1][y1] == target || matrix[x1][y1+1] == target)
return true;
else
return false;
}
// 取出矩阵的中心点
int midx = (x1 + x2) / 2, midy = (y1 + y2) / 2;
int midval = (matrix[midx][midy]);
// 搜索其他三个区域
if (midval == target)
return true;
if (midval < target)
return binarySearch(matrix,target,x1,midy,midx,y2)
||binarySearch(matrix,target,midx,y1,x2,midy)
||binarySearch(matrix,target,midx,midy,x2,y2);
else if (midval > target)
return binarySearch(matrix,target,x1,midy,midx,y2)
||binarySearch(matrix,target,midx,y1,x2,midy)
||binarySearch(matrix,target,x1,y1,midx,midy);
return false;
}
bool searchMatrix(vector<vector<int>>& matrix, int target) {
int m = matrix.size();
if (m == 0 )
return false;
int n = matrix[0].size();
if (n==0)
return false;
return binarySearch(matrix, target, 0, 0, m-1, n-1);
}
};
int main()
{
vector<vector<int> > matrix;
int r1[5] = {1,4,7,11,15};
int r2[5] = {2,5,8,12,19};
int r3[5] = {3,6,9,16,22};
int r4[5] = {10,13,14,17,24};
int r5[5] = {18,21,23,26,30};
int *row[5] = {r1,r2,r3,r4,r5};
for (int i=0; i<5; i++)
{
vector<int> tmp(row[i], row[i]+5);
matrix.push_back(tmp);
}
Solution su;
cout<<su.searchMatrix(matrix, 5);
return 0;
}