題目敘述
Write an efficient algorithm that searches for a value target in an m x n integer matrix matrix. This matrix has the following properties:
- Integers in each row are sorted from left to right.
- The first integer of each row is greater than the last integer of the previous row.
Example 1:
Input: matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 3
Output: true
Example 2:
Input: matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 13
Output: false
Constraints:
m == matrix.lengthn == matrix[i].length1 <= m, n <= 100-10**4 <= matrix[i][j], target <= 10**4
題目翻譯
今天有一個 m x n 的二維矩陣，和一個 target 的參數。其中 matrix 的值是由小到大排序，當第一列排完後接續第二列。然後要在這個二維矩陣中找出是否包含 target 的值。
解法解析
我一開始的解題思路是，先跟每一列的第一個元素是做比較，查出說是在哪一列，第二步在針對那一列作搜尋。不過看了其他人的解題思路，才發現自己第一步多餘了，其實二維矩陣就是一個大的排序過的陣列，所以直接對其做 Binary Search 即可，唯一要處理的是怎麼從 index 轉換成行列的位置。
解法範例
Go
func searchMatrix(matrix [][]int, target int) bool {
m := len(matrix)
if m == 0 {
return false
}
n := len(matrix[0])
for left, right := 0, m*n-1; left <= right; {
pivotIdx := (left + right) / 2
pivotElement := matrix[pivotIdx/n][pivotIdx%n]
if pivotElement == target {
return true
} else if target < pivotElement {
right = pivotIdx - 1
} else {
left = pivotIdx + 1
}
}
return false
}
JavaScript
var searchMatrix = function (matrix, target) {
const m = matrix.length;
if (m === 0) return false;
const n = matrix[0].length;
for (let left = 0, right = m * n - 1; left <= right; ) {
const pivotIdx = Math.floor((left + right) / 2);
const pivotElement = matrix[Math.floor(pivotIdx / n)][pivotIdx % n];
if (pivotElement === target) return true;
if (target < pivotElement) right = pivotIdx - 1;
else left = pivotIdx + 1;
}
return false;
};
Kotlin
class Solution {
fun searchMatrix(matrix: Array<IntArray>, target: Int): Boolean {
if (matrix.isEmpty()) return false
val m = matrix.size
val n = matrix[0].size
var left = 0
var right = m * n - 1
while (left <= right) {
val pivotIdx = (right + left) / 2
val pivotElement = matrix[pivotIdx / n][pivotIdx % n]
if (pivotElement == target) {
return true
} else if (pivotElement < target) {
left = pivotIdx + 1
} else {
right = pivotIdx - 1
}
}
}
}
PHP
class Solution
{
function searchMatrix($matrix, $target)
{
$m = count($matrix);
if ($m == 0) {
return false;
}
$n = count($matrix[0]);
$left = 0;
$right = $m * $n - 1;
while ($left <= $right) {
$pivotIdx = (int)(($left + $right) / 2);
$pivotElement = $matrix[(int)($pivotIdx / $n)][$pivotIdx % $n];
if ($pivotElement == $target) {
return true;
} else if ($pivotElement < $target) {
$left = $pivotIdx + 1;
} else {
$right = $pivotIdx - 1;
}
}
return false;
}
}
Python
class Solution:
def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
m = len(matrix)
if m == 0:
return False
n = len(matrix[0])
left, right = 0, m * n - 1
while left <= right:
pivot_idx = (left + right) // 2
pivot_element = matrix[pivot_idx // n][pivot_idx % n]
if target == pivot_element:
return True
elif target < pivot_element:
right = pivot_idx - 1
else:
left = pivot_idx + 1
return False
Rust
impl Solution {
pub fn search_matrix(matrix: Vec<Vec<i32>>, target: i32) -> bool {
if matrix.is_empty() {
return false;
}
let m = matrix.len();
let n = matrix[0].len();
let (mut left, mut right) = (0, m * n);
while left < right {
let pivot_idx = (left + right) / 2;
let pivot_element = matrix[pivot_idx / n][pivot_idx % n];
if target == pivot_element {
return true;
} else if target < pivot_element {
right = pivot_idx;
} else {
left = pivot_idx + 1;
}
}
false
}
}
Swift
class Solution {
func searchMatrix(_ matrix: [[Int]], _ target: Int) -> Bool {
let m = matrix.count
guard m > 0 else { return false }
let n = matrix[0].count
var left = 0, right = m * n - 1
while left <= right {
let pivotIdx = (left + right) / 2
let pivotElement = matrix[pivotIdx / n][pivotIdx % n]
if pivotElement == target {
return true
} else if target < pivotElement {
right = pivotIdx - 1
} else {
left = pivotIdx + 1
}
}
return false
}
}