文章目錄

• • 1. 題目
  • 2. 解題
  • • 2.1 從左下角或者右上角開始搜索
    • 2.2 分治算法

1. 題目

編寫一個高效的算法來搜索 m x n 矩陣 matrix 中的一個目標(biāo)值 target。該矩陣具有以下特性：

每行的元素從左到右升序排列。
每列的元素從上到下升序排列。

示例: 現(xiàn)有矩陣 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。

類似題目：
LeetCode 74. 搜索二維矩陣（二分查找）
程序員面試金典 - 面試題 10.09. 排序矩陣查找

來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/search-a-2d-matrix-ii
著作權(quán)歸領(lǐng)扣網(wǎng)絡(luò)所有。商業(yè)轉(zhuǎn)載請聯(lián)系官方授權(quán)，非商業(yè)轉(zhuǎn)載請注明出處。

2. 解題

2.1 從左下角或者右上角開始搜索

• 在左下角或者右下角，以所在點形成的L形狀是有序的，根據(jù)大小選擇走的方向
• 時間復(fù)雜度O（m+n）

class Solution { public:bool searchMatrix(vector<vector<int>>& matrix, int target) {if(matrix.size()==0 || matrix[0].size() == 0)return false;int r = matrix.size(), c = matrix[0].size();int x = r-1, y = 0;//左下角while(x>=0 && y<c){if(matrix[x][y] == target)return true;else if(matrix[x][y] < target)y++;elsex--;}return false;} };

or

class Solution { public:bool searchMatrix(vector<vector<int>>& matrix, int target) {if(matrix.size()==0 || matrix[0].size() == 0)return false;int r = matrix.size(), c = matrix[0].size();int x = 0, y = c-1;//右上角while(x<r && y>=0){if(matrix[x][y] == target)return true;else if(matrix[x][y] < target)x++;elsey--;}return false;} };

2.2 分治算法

• 左端點為矩陣左上角，右端點為矩陣右下角，按坐標(biāo)取中
• target 比 9 大，那么 下圖左上角子矩陣肯定不存在，在余下3塊中查找(紅色)
• target 比 9 小，那么 下圖右下角子矩陣肯定不存在，在余下3塊中查找(藍(lán)色)
• 時間復(fù)雜度O((m*n)的log4為底的3次冪) ，近似為（mn）^0.8
  時間復(fù)雜度遞推公式 $O(T)=3O(T/4)+O(1)$

$f(T)=\frac{3}{2}?3^{{\log }_4^{(mn)}}\approx O((mn{)}^{0.8})$

class Solution {int m,n; public:bool searchMatrix(vector<vector<int>>& matrix, int target) {if(matrix.size()==0 || matrix[0].size() == 0)return false;int r = matrix.size(), c = matrix[0].size();m = r, n = c;int x1 = 0, y1 = 0, x2 = r-1, y2 = c-1, mx, my;bool ans = false;return search(matrix,target,x1,y1,x2,y2,ans);}bool search(vector<vector<int>> &matrix, int &target, int x1, int y1, int x2, int y2, bool &ans){if(ans)return true;if(x1 > x2 || y1 > y2 ||x1<0||x1>=m||x2<0||x2>=m||y1<0||y1>=n||y2<0||y2>=n)return false;int mx = x1+((x2-x1)>>1);int my = y1+((y2-y1)>>1);if(matrix[mx][my] == target){ans = true;return ans;}if(matrix[mx][my] < target){search(matrix,target,x1,my+1,mx,y2,ans)|| search(matrix,target,mx+1,y1,x2,my,ans)|| search(matrix,target,mx+1,my+1,x2,y2,ans);return ans;}else{search(matrix,target,x1,my,mx-1,y2,ans)|| search(matrix,target,mx,y1,x2,my-1,ans)|| search(matrix,target,x1,y1,mx-1,my-1,ans);return ans;}} };

總結(jié)

以上是生活随笔為你收集整理的LeetCode 240. 搜索二维矩阵 II（二分查找 分治）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。