74. Search a 2D Matrix
給定一個 m x n 的整數矩陣 matrix，該矩陣具有以下兩個屬性：每一行都是按非遞減順序排列的。
每一行的第一個整數都大於前一行的最後一個整數。
給定一個整數 target，如果 target 在矩陣中，返回 true；否則返回 false。
你必須編寫一個時間複雜度為 O(log(m * n)) 的解決方案。
範例 1：
輸入：matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 3 輸出：true
Python
class Solution:
def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
if not matrix or not matrix[0]:
return False
m, n = len(matrix), len(matrix[0])
left, right = 0, m * n - 1
while left <= right:
mid = left + (right - left) // 2
mid_value = matrix[mid // n][mid % n]
if mid_value == target:
return True
elif mid_value < target:
left = mid + 1
else:
right = mid - 1
return False
17.02MB, 54ms
C++
#include <vector>
using namespace std;
class Solution {
public:
bool searchMatrix(vector<vector<int>>& matrix, int target) {
if (matrix.empty() || matrix[0].empty()) {
return false;
}
int m = matrix.size();
int n = matrix[0].size();
int left = 0;
int right = m * n - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
int mid_value = matrix[mid / n][mid % n];
if (mid_value == target) {
return true;
} else if (mid_value < target) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return false;
}
};
12.04MB, 7ms
Javascript
/**
* @param {number[][]} matrix
* @param {number} target
* @return {boolean}
*/
var searchMatrix = function(matrix, target) {
if (matrix.length === 0 || matrix[0].length === 0) {
return false;
}
const m = matrix.length;
const n = matrix[0].length;
let left = 0;
let right = m * n - 1;
while (left <= right) {
const mid = Math.floor((left + right) / 2);
const mid_value = matrix[Math.floor(mid / n)][mid % n];
if (mid_value === target) {
return true;
} else if (mid_value < target) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return false;
};
48.99MB, 51ms
