class Solution {
public:
bool searchMatrix(vector<vector<int>>& matrix, int target) {
}
};
面试题 10.09. 排序矩阵查找
给定M×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。
原站题解
golang 解法, 执行用时: 20 ms, 内存消耗: 6.5 MB, 提交时间: 2022-11-30 22:16:20
func searchMatrix(matrix [][]int, target int) bool {
if len(matrix) == 0 || len(matrix[0]) == 0 {
return false
}
m, n := len(matrix), len(matrix[0])
x, y := 0, n-1
for x < m && y >= 0 {
if matrix[x][y] == target {
return true
}
if matrix[x][y] > target {
y--
} else {
x++
}
}
return false
}
javascript 解法, 执行用时: 60 ms, 内存消耗: 43.8 MB, 提交时间: 2022-11-30 22:16:08
/**
* @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, n = matrix[0].length;
let x = 0, y = n - 1;
while (x < m && y >= 0) {
if (matrix[x][y] === target) {
return true;
}
if (matrix[x][y] > target) {
--y;
} else {
++x;
}
}
return false;
};
python3 解法, 执行用时: 44 ms, 内存消耗: 19.6 MB, 提交时间: 2022-11-30 22:15:54
class Solution:
def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
if len(matrix) == 0 or len(matrix[0]) == 0:
return False
m, n = len(matrix), len(matrix[0])
x, y = 0, n - 1
while x < m and y >= 0:
if matrix[x][y] == target:
return True
if matrix[x][y] > target:
y -= 1
else:
x += 1
return False
python3 解法, 执行用时: 52 ms, 内存消耗: 19.6 MB, 提交时间: 2022-11-30 22:15:12
class Solution:
def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
if len(matrix) == 0 or len(matrix[0]) == 0:
return False
for row in matrix:
idx = bisect.bisect_left(row, target)
if idx < len(row) and row[idx] == target:
return True
return False
golang 解法, 执行用时: 24 ms, 内存消耗: 6.5 MB, 提交时间: 2022-11-30 22:14:43
func searchMatrix(matrix [][]int, target int) bool {
if len(matrix) == 0 || len(matrix[0]) == 0 {
return false
}
for _, row := range matrix {
i := sort.SearchInts(row, target)
if i < len(row) && row[i] == target {
return true
}
}
return false
}
javascript 解法, 执行用时: 228 ms, 内存消耗: 44.2 MB, 提交时间: 2022-11-30 22:14:30
/**
* @param {number[][]} matrix
* @param {number} target
* @return {boolean}
*/
var searchMatrix = function(matrix, target) {
if (matrix.length == 0 || matrix[0].length == 0) {
return false;
}
for (const row of matrix) {
const index = search(row, target);
if (index >= 0) {
return true;
}
}
return false;
};
const search = (nums, target) => {
let low = 0, high = nums.length - 1;
while (low <= high) {
const mid = Math.floor((high - low) / 2) + low;
const num = nums[mid];
if (num === target) {
return mid;
} else if (num > target) {
high = mid - 1;
} else {
low = mid + 1;
}
}
return -1;
}
golang 解法, 执行用时: 20 ms, 内存消耗: 6.5 MB, 提交时间: 2022-11-30 22:14:11
func searchMatrix(matrix [][]int, target int) bool {
if len(matrix) == 0 || len(matrix[0]) == 0 {
return false
}
for _, row := range matrix {
for _, v := range row {
if v == target {
return true
}
}
}
return false
}
python3 解法, 执行用时: 48 ms, 内存消耗: 19.7 MB, 提交时间: 2022-11-30 22:13:57
class Solution:
def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
if len(matrix) == 0 or len(matrix[0]) == 0:
return False
for row in matrix:
for element in row:
if element == target:
return True
return False