04.二维数组中的查找.md

04. 二维数组中的查找

https://leetcode-cn.com/problems/er-wei-shu-zu-zhong-de-cha-zhao-lcof/

Java

/*
 * @Author: Goog Tech
 * @Date: 2020-08-30 18:00:35
 * @LastEditTime: 2020-08-30 18:00:46
 * @Description: https://leetcode-cn.com/problems/er-wei-shu-zu-zhong-de-cha-zhao-lcof/
 * @FilePath: \leetcode-googtech\剑指 Offer\#04. 二维数组中的查找\Solution.java
 * @WebSite: https://algorithm.show/
 */

class Solution {
    
    // 从右上角开始走，利用这个顺序关系可以在 O(m + n) 的复杂度下解决这个题:
    // 1. 如果当前位置元素比 target 小,则 row++
    // 2. 如果当前位置元素比 target大,则 col--
    // 3. 如果相等则返回 true
    // 4. 如果越界了还没找到则说明不存在,返回 false
    public boolean findNumberIn2DArray(int[][] matrix, int target) {
        if(matrix == null || matrix.length == 0) return false;
        int row = 0, col = matrix[0].length - 1;
        while(row < matrix.length && col >= 0) {
            if(matrix[row][col] > target) {
                col--;
            }else if(matrix[row][col] < target) {
                row++;
            }else {
                return true;
            }
        }
        return false;
    }
}

Python

'''
Author: Goog Tech
Date: 2020-08-30 18:00:40
LastEditTime: 2020-08-30 18:01:01
Description: https://leetcode-cn.com/problems/er-wei-shu-zu-zhong-de-cha-zhao-lcof/
FilePath: \leetcode-googtech\剑指 Offer\#04. 二维数组中的查找\Solution.py
WebSite: https://algorithm.show/
'''

class Solution(object):

    # 从右上角开始走，利用这个顺序关系可以在 O(m + n) 的复杂度下解决这个题:
    # 1. 如果当前位置元素比 target 小,则 row++
    # 2. 如果当前位置元素比 target大,则 col--
    # 3. 如果相等则返回 true
    # 4. 如果越界了还没找到则说明不存在,返回 false
    def findNumberIn2DArray(self, matrix, target):
        """
        :type matrix: List[List[int]]
        :type target: int
        :rtype: bool
        """
        if len(matrix) == 0 or len(matrix[0]) == 0: return False
        n, m = len(matrix), len(matrix[0])
        row, column = 0, m - 1
        while row <= n - 1 and column >= 0:
            if matrix[row][column] == target:
                return True
            elif matrix[row][column] > target:
                column -= 1
            else:
                row += 1
        return False