資料結構
網路
關係資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化學
生物
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究C++ 中的二維矩陣搜尋
假設我們需要編寫一個高效的演算法來在一個 m x n 矩陣中搜索一個值。這個矩陣有一些如下屬性：
- 每一行從左到右排序
- 每一行的第一個數字大於前一行的最後一個整數。
所以如果矩陣如下：
| 1 | 3 | 5 | 7 |
| 10 | 11 | 16 | 20 |
| 23 | 30 | 34 | 50 |
| 53 | 62 | 78 | 98 |
如果目標值為 16，則輸出為 True。
讓我們看看步驟：
- n := 行數，如果 n 為 0，則返回 false，m := 列數，如果 m 為 0，則返回 false
- low := 0 且 high := n – 1
- 當 low < high
- mid := low + (high – low + 1)/2
- 如果 mat[mid, 0] <= target，則 low := mid，否則 high := mid – 1
- rlow := 0 且 rhigh := m – 1 且 ans := 0
- 當 rlow <= rhigh
- mid := rlow + (rhigh - rlow)/2
- 如果 mat[low, mid] = target，則 ans := 1，並退出迴圈
- 否則，當 matrix[low, mid] < target 時，則 rlow := mid + 1
- 否則 rhigh := mid – 1
- 返回 ans
讓我們看看下面的實現來更好地理解：
示例
#include <bits/stdc++.h>
using namespace std;
typedef long long int lli;
class Solution {
public:
bool searchMatrix(vector<vector<int>>& matrix, int target) {
lli n,m;
n = matrix.size();
if(!n)return false;
m = matrix[0].size();
if(!m)return false;
lli low = 0, high = n-1;
while(low<high){
lli mid = low + ( high - low +1)/2;
if(matrix[mid][0]<=target)low = mid;
else high = mid -1;
}
lli rlow = 0, rhigh = m-1;
lli ans = 0;
while(rlow<=rhigh){
lli mid = rlow+(rhigh - rlow)/2;
if(matrix[low][mid] == target){
ans =1;
break;
}else if(matrix[low][mid]<target)rlow=mid+1;
else rhigh= mid-1;
}
return ans;
}
};
main(){
Solution ob;
vector<vector<int>> v = {{1,3,5,7},{10,11,16,20},{23,30,34,50},{53,62,78,98}};
cout << ob.searchMatrix(v, 16);
}輸入
[[1,3,5,7],[10,11,16,20],[23,30,34,50],[53,62,78,98]] 16
輸出
1
更新於: 2020年5月4日
335 次檢視
廣告