Skip to content

Latest commit

 

History

History
361 lines (301 loc) · 8.22 KB

README.md

File metadata and controls

361 lines (301 loc) · 8.22 KB

240. 搜索二维矩阵 II

English Version

题目描述

编写一个高效的算法来搜索 m x n 矩阵 matrix 中的一个目标值 target 。该矩阵具有以下特性：

  • 每行的元素从左到右升序排列。
  • 每列的元素从上到下升序排列。

 

示例 1：

输入：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

示例 2：

输入：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 = 20
输出：false

 

提示：

  • m == matrix.length
  • n == matrix[i].length
  • 1 <= n, m <= 300
  • -109 <= matrix[i][j] <= 109
  • 每行的所有元素从左到右升序排列
  • 每列的所有元素从上到下升序排列
  • -109 <= target <= 109

解法

方法一：二分查找

由于每一行升序排列，因此可以对每一行执行二分查找。

时间复杂度 $O(mlogn)$。

方法二：从左下角或右上角搜索

这里我们以左下角作为起始搜索点，往右上方向开始搜索，比较当前元素 matrix[i][j]与 target 的大小关系：

  • 若 matrix[i][j] == target，说明找到了目标值，直接返回 true。
  • 若 matrix[i][j] > target，说明这一行从当前位置开始往右的所有元素均大于 target，应该让 i 指针往上移动，即 i--。
  • 若 matrix[i][j] < target，说明这一列从当前位置开始往上的所有元素均小于 target，应该让 j 指针往右移动，即 j++。

若搜索结束依然找不到 target，返回 false。

时间复杂度 $O(m+n)$。

Python3

二分查找：

class Solution:
    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
        n = len(matrix[0])
        for row in matrix:
            idx = bisect_left(row, target)
            if idx != n and row[idx] == target:
                return True
        return False

从左下角或右上角搜索：

class Solution:
    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
        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 False

Java

二分查找：

class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        for (int[] row : matrix) {
            int idx = Arrays.binarySearch(row, target);
            if (idx >= 0) {
                return true;
            }
        }
        return false;
    }
}

从左下角或右上角搜索：

class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        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;
    }
}

TypeScript

二分查找：

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;
}

从左下角或右上角搜索：

function searchMatrix(matrix: number[][], target: number): boolean {
    let m = matrix.length,
        n = matrix[0].length;
    let i = m - 1,
        j = 0;
    while (i >= 0 && j < n) {
        let cur = matrix[i][j];
        if (cur == target) return true;
        if (cur > target) {
            --i;
        } else {
            ++j;
        }
    }
    return false;
}

C++

二分查找：

class Solution {
public:
    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        int n = matrix[0].size();
        for (auto& row : matrix) {
            int idx = lower_bound(row.begin(), row.end(), target) - row.begin();
            if (idx != n && row[idx] == target) return true;
        }
        return false;
    }
};

从左下角或右上角搜索：

class Solution {
public:
    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        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;
    }
};

Go

二分查找：

func searchMatrix(matrix [][]int, target int) bool {
	n := len(matrix[0])
	for _, row := range matrix {
		left, right := 0, n
		for left < right {
			mid := (left + right) >> 1
			if row[mid] >= target {
				right = mid
			} else {
				left = mid + 1
			}
		}
		if left != n && row[left] == target {
			return true
		}
	}
	return false
}

从左下角或右上角搜索：

func searchMatrix(matrix [][]int, target int) bool {
	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
}

C#

public class Solution {
    public bool SearchMatrix(int[][] matrix, int target) {
        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;
    }
}

Rust

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
    }
}

JavaScript

/**
 * @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;
};

...