<reponame>joey66666/Codeyard
#
# @lc app=leetcode.cn id=240 lang=python3
#
# [240] 搜索二维矩阵 II
#
# https://leetcode-cn.com/problems/search-a-2d-matrix-ii/description/
#
# algorithms
# Medium (47.92%)
# Likes:    767
# Dislikes: 0
# Total Accepted:    176.5K
# Total Submissions: 366.7K
# Testcase Example:  '[[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]]\n' +
# '5'
#
# 编写一个高效的算法来搜索 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
# -10^9 <= matrix[i][j] <= 10^9
# 每行的所有元素从左到右升序排列
# 每列的所有元素从上到下升序排列
# -10^9 <= target <= 10^9
#
#
#

# @lc code=start
"""
1. Solution1, 单行双指针, Time: (mlogn), Space: O(1), Runtime: 85%
  - 纵向遍历，每行再左右双指针往中间遍历
"""

class Solution:
    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
        rows, cols = len(matrix), len(matrix[0])
        for row in range(rows):
            if matrix[row][0] <= target <= matrix[row][cols - 1]:
                left, right = 0, cols - 1
                while left <= right:
                    if matrix[row][left] == target or matrix[row][right] == target:
                        return True
                    left += 1
                    right -= 1
        return False

"""
2. Solution2, 行列双指针, Time: O(logmlogn), Space: O(1), Runtime: 97%
  - 纵向确定上下range，再对range内每行左右双指针往中间遍历
"""

class Solution:
    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
        rows, cols = len(matrix), len(matrix[0])
        low, high = 0, rows - 1
        while matrix[low][0] > target and low < rows - 1:
            low += 1
        while matrix[high][0] > target and high > 0:
            high -= 1

        for row in range(low, high + 1):
            if matrix[row][0] <= target <= matrix[row][cols - 1]:
                left, right = 0, cols - 1
                while left <= right:
                    if matrix[row][left] == target or matrix[row][right] == target:
                        return True
                    left += 1
                    right -= 1
        return False

"""
3. Solution3, Z型遍历, Time: O(m + n), Space: O(1), Runtime: 93%
  - 从右上角往左下角遍历
  - `matrix[i][j] == target: return True`
  - `matrix[i][j] > target`，因为每列为ascending，所以`matrix[i][j]`所在列都 `> target`, 所以向左移一列
  - `matrix[i][j] < target`，因为每行为ascending，所以`matrix[i][j]`所在行都 `< target`, 所以向下移一行
"""
class Solution:
    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
        rows, cols = len(matrix), len(matrix[0])
        i, j = 0, cols - 1
        while i < rows and j >= 0:
            if matrix[i][j] == target:
                return True
            elif matrix[i][j] > target:
                j -= 1
            else:
                i += 1
                
        return False

# @lc code=end

#
# @lc app=leetcode.cn id=240 lang=python3
#
# [240] 搜索二维矩阵 II
#
# https://leetcode-cn.com/problems/search-a-2d-matrix-ii/description/
#
# algorithms
# Medium (47.92%)
# Likes:    767
# Dislikes: 0
# Total Accepted:    176.5K
# Total Submissions: 366.7K
# Testcase Example:  '[[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]]\n' +
# '5'
#
# 编写一个高效的算法来搜索 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
# -10^9 <= matrix[i][j] <= 10^9
# 每行的所有元素从左到右升序排列
# 每列的所有元素从上到下升序排列
# -10^9 <= target <= 10^9
#
#
#

# @lc code=start
"""
1. Solution1, 单行双指针, Time: (mlogn), Space: O(1), Runtime: 85%
  - 纵向遍历，每行再左右双指针往中间遍历
"""

class Solution:
    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
        rows, cols = len(matrix), len(matrix[0])
        for row in range(rows):
            if matrix[row][0] <= target <= matrix[row][cols - 1]:
                left, right = 0, cols - 1
                while left <= right:
                    if matrix[row][left] == target or matrix[row][right] == target:
                        return True
                    left += 1
                    right -= 1
        return False

"""
2. Solution2, 行列双指针, Time: O(logmlogn), Space: O(1), Runtime: 97%
  - 纵向确定上下range，再对range内每行左右双指针往中间遍历
"""

class Solution:
    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
        rows, cols = len(matrix), len(matrix[0])
        low, high = 0, rows - 1
        while matrix[low][0] > target and low < rows - 1:
            low += 1
        while matrix[high][0] > target and high > 0:
            high -= 1

        for row in range(low, high + 1):
            if matrix[row][0] <= target <= matrix[row][cols - 1]:
                left, right = 0, cols - 1
                while left <= right:
                    if matrix[row][left] == target or matrix[row][right] == target:
                        return True
                    left += 1
                    right -= 1
        return False

"""
3. Solution3, Z型遍历, Time: O(m + n), Space: O(1), Runtime: 93%
  - 从右上角往左下角遍历
  - `matrix[i][j] == target: return True`
  - `matrix[i][j] > target`，因为每列为ascending，所以`matrix[i][j]`所在列都 `> target`, 所以向左移一列
  - `matrix[i][j] < target`，因为每行为ascending，所以`matrix[i][j]`所在行都 `< target`, 所以向下移一行
"""
class Solution:
    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
        rows, cols = len(matrix), len(matrix[0])
        i, j = 0, cols - 1
        while i < rows and j >= 0:
            if matrix[i][j] == target:
                return True
            elif matrix[i][j] > target:
                j -= 1
            else:
                i += 1
                
        return False

# @lc code=end
# # @lc app=leetcode.cn id=240 lang=python3 # # [240] 搜索二维矩阵 II # # https://leetcode-cn.com/problems/search-a-2d-matrix-ii/description/ # # algorithms # Medium (47.92%) # Likes:    767 # Dislikes: 0 # Total Accepted:    176.5K # Total Submissions: 366.7K # Testcase Example:  '[[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]]\n' + # '5' # # 编写一个高效的算法来搜索 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 # -10^9 <= matrix[i][j] <= 10^9 # 每行的所有元素从左到右升序排列 # 每列的所有元素从上到下升序排列 # -10^9 <= target <= 10^9 # # # # @lc code=start 1. Solution1, 单行双指针, Time: (mlogn), Space: O(1), Runtime: 85%   - 纵向遍历，每行再左右双指针往中间遍历 2. Solution2, 行列双指针, Time: O(logmlogn), Space: O(1), Runtime: 97%   - 纵向确定上下range，再对range内每行左右双指针往中间遍历 3. Solution3, Z型遍历, Time: O(m + n), Space: O(1), Runtime: 93%   - 从右上角往左下角遍历   - `matrix[i][j] == target: return True`   - `matrix[i][j] > target`，因为每列为ascending，所以`matrix[i][j]`所在列都 `> target`, 所以向左移一列   - `matrix[i][j] < target`，因为每行为ascending，所以`matrix[i][j]`所在行都 `< target`, 所以向下移一行 # @lc code=end