| comments | difficulty | edit_url |
|---|---|---|
true |
中等 |
给定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。
由于每一行的所有元素升序排列，因此，对于每一行，我们可以使用二分查找找到第一个大于等于 target 的元素，然后判断该元素是否等于 target。如果等于 target，说明找到了目标值，直接返回 true。如果不等于 target，说明这一行的所有元素都小于 target，应该继续搜索下一行。
如果所有行都搜索完了，都没有找到目标值，说明目标值不存在，返回 false。
时间复杂度
class Solution:
def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
for row in matrix:
j = bisect_left(row, target)
if j < len(matrix[0]) and row[j] == target:
return True
return Falseclass Solution {
public boolean searchMatrix(int[][] matrix, int target) {
for (var row : matrix) {
int j = Arrays.binarySearch(row, target);
if (j >= 0) {
return true;
}
}
return false;
}
}class Solution {
public:
bool searchMatrix(vector<vector<int>>& matrix, int target) {
for (auto& row : matrix) {
int j = lower_bound(row.begin(), row.end(), target) - row.begin();
if (j < matrix[0].size() && row[j] == target) {
return true;
}
}
return false;
}
};func searchMatrix(matrix [][]int, target int) bool {
for _, row := range matrix {
j := sort.SearchInts(row, target)
if j < len(matrix[0]) && row[j] == target {
return true
}
}
return false
}function searchMatrix(matrix: number[][], target: number): boolean {
const n = matrix[0].length;
for (const row of matrix) {
let left = 0,
right = n;
while (left < right) {
const mid = (left + right) >> 1;
if (row[mid] >= target) {
right = mid;
} else {
left = mid + 1;
}
}
if (left != n && row[left] == target) {
return true;
}
}
return false;
}use std::cmp::Ordering;
impl Solution {
pub fn search_matrix(matrix: Vec<Vec<i32>>, target: i32) -> bool {
let m = matrix.len();
let n = matrix[0].len();
let mut i = 0;
let mut j = n;
while i < m && j > 0 {
match target.cmp(&matrix[i][j - 1]) {
Ordering::Less => {
j -= 1;
}
Ordering::Greater => {
i += 1;
}
Ordering::Equal => {
return true;
}
}
}
false
}
}/**
* @param {number[][]} matrix
* @param {number} target
* @return {boolean}
*/
var searchMatrix = function (matrix, target) {
const n = matrix[0].length;
for (const row of matrix) {
let left = 0,
right = n;
while (left < right) {
const mid = (left + right) >> 1;
if (row[mid] >= target) {
right = mid;
} else {
left = mid + 1;
}
}
if (left != n && row[left] == target) {
return true;
}
}
return false;
};public class Solution {
public bool SearchMatrix(int[][] matrix, int target) {
foreach (int[] row in matrix) {
int j = Array.BinarySearch(row, target);
if (j >= 0) {
return true;
}
}
return false;
}
}class Solution {
func searchMatrix(_ matrix: [[Int]], _ target: Int) -> Bool {
for row in matrix {
if binarySearch(row, target) {
return true
}
}
return false
}
private func binarySearch(_ array: [Int], _ target: Int) -> Bool {
var left = 0
var right = array.count - 1
while left <= right {
let mid = left + (right - left) / 2
if array[mid] == target {
return true
} else if array[mid] < target {
left = mid + 1
} else {
right = mid - 1
}
}
return false
}
}这里我们以左下角作为起始搜索点，往右上方向开始搜索，比较当前元素 matrix[i][j]与 target 的大小关系：
- 若
$\textit{matrix}[i][j] = \textit{target}$ ，说明找到了目标值，直接返回true。 - 若
$\textit{matrix}[i][j] > \textit{target}$ ，说明这一列从当前位置开始往上的所有元素均大于target，应该让$i$ 指针往上移动，即$i \leftarrow i - 1$ 。 - 若
$\textit{matrix}[i][j] < \textit{target}$ ，说明这一行从当前位置开始往右的所有元素均小于target，应该让$j$ 指针往右移动，即$j \leftarrow j + 1$ 。
若搜索结束依然找不到 target，返回 false。
时间复杂度
class Solution:
def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
if not matrix:
return False
m, n = len(matrix), len(matrix[0])
i, j = m - 1, 0
while i >= 0 and j < n:
if matrix[i][j] == target:
return True
if matrix[i][j] > target:
i -= 1
else:
j += 1
return Falseclass Solution {
public boolean searchMatrix(int[][] matrix, int target) {
if (matrix == null || matrix.length == 0) {
return false;
}
int m = matrix.length, n = matrix[0].length;
int i = m - 1, j = 0;
while (i >= 0 && j < n) {
if (matrix[i][j] == target) {
return true;
}
if (matrix[i][j] > target) {
--i;
} else {
++j;
}
}
return false;
}
}class Solution {
public:
bool searchMatrix(vector<vector<int>>& matrix, int target) {
if (matrix.empty()) {
return false;
}
int m = matrix.size(), n = matrix[0].size();
int i = m - 1, j = 0;
while (i >= 0 && j < n) {
if (matrix[i][j] == target) {
return true;
}
if (matrix[i][j] > target) {
--i;
} else {
++j;
}
}
return false;
}
};func searchMatrix(matrix [][]int, target int) bool {
if len(matrix) == 0 {
return false
}
m, n := len(matrix), len(matrix[0])
i, j := m-1, 0
for i >= 0 && j < n {
if matrix[i][j] == target {
return true
}
if matrix[i][j] > target {
i--
} else {
j++
}
}
return false
}function searchMatrix(matrix: number[][], target: number): boolean {
if (matrix.length === 0) {
return false;
}
const [m, n] = [matrix.length, matrix[0].length];
let [i, j] = [m - 1, 0];
while (i >= 0 && j < n) {
if (matrix[i][j] === target) {
return true;
}
if (matrix[i][j] > target) {
--i;
} else {
++j;
}
}
return false;
}public class Solution {
public bool SearchMatrix(int[][] matrix, int target) {
if (matrix.Length == 0) {
return false;
}
int m = matrix.Length, n = matrix[0].Length;
int i = m - 1, j = 0;
while (i >= 0 && j < n) {
if (matrix[i][j] == target) {
return true;
}
if (matrix[i][j] > target) {
--i;
} else {
++j;
}
}
return false;
}
}