# LeetCode Medium 240. Search a 2D Matrix II

tags: leetcode

問題

• Explore
• Problems

$m \times n$行列からある値を取り出す効率的なアルゴリズムを書け.この行列は以下の特徴がある

• 各行の整数は昇順に左から右へ整列されている
• 各列の整数は昇順に上から下へ整列されている

解法1(recursive)

再帰的に解くことが可能です

• 基底は再帰関数で要素が見つかった時と見つからないときです
  • 行と列の添字をそれぞれy, xとしてmatrix[y][x]が求める値であるときはTRUE
  • yもしくはxが行列の範囲外を参照したらFALSEとします
• それ以外では行列を大きさに応じて探索をします
  • 最初にy = 0, x = 行列の行数とします
  • matrix[y][x]が目的の値よりも小さいならば, 昇順なのでyがより大きい場所にあります
  • そうでないときはmatrix[y][x]は目的の値以上なので, xがより小さい場所にあります

計算量

• 空間計算量は最悪$O(n+m)$回再帰関数を実行する必要があるので$O(n+m)です
• 時間計算量は同様の理由で$O(n+m)$です

Python

class Solution:
    def searchMatrix(self, matrix, target):
        """
        :type matrix: List[List[int]]
        :type target: int
        :rtype: bool
        """
        def helper(matrix, y, x, target):
          if len(matrix) <= y or x < 0:
            return False
          if matrix[y][x] == target:
            return True
          
          if matrix[y][x] < target:
            return helper(matrix, y+1, x, target)
          else:
            return helper(matrix, y, x-1, target)
        
        if len(matrix) == 0 or len(matrix[0]) == 0:
          return False
        
        row = len(matrix[0]) - 1
        return helper(matrix, 0, row, target)

C++

class Solution {
 public:
  bool searchMatrix(vector<vector<int>>& matrix, int target) {
    if (matrix.size() == 0 || matrix[0].size() == 0) return false;

    int row = matrix[0].size() - 1;
    return helper(matrix, 0, row, target);
  }

 private:
  bool helper(vector<vector<int>>& matrix, int y, int x, int target) {
    if (matrix.size() <= y || x < 0) return false;
    if (matrix[y][x] == target) return true;

    if (matrix[y][x] < target)
      return helper(matrix, y + 1, x, target);
    else
      return helper(matrix, y, x - 1, target);
  }
};

解法2(iterative)

上記の手法をiterativeにするにはwhile文などで処理するだけです

計算量

• 空間計算量は既存の行列を使うので$O(1)$
• 時間計算量は上と同様に$O(n + m)$

Python

class Solution:
    def searchMatrix(self, matrix, target):
        """
        :type matrix: List[List[int]]
        :type target: int
        :rtype: bool
        """
        if len(matrix) == 0 or len(matrix[0]) == 0:
          return False
        
        y, x = 0, len(matrix[0]) - 1
        
        while y < len(matrix) and 0 <= x:
          if matrix[y][x] == target:
            return True
          
          if matrix[y][x] < target:
            y += 1
          else:
            x -= 1
            
        return False

C++

class Solution {
public:    
    bool searchMatrix(vector<vector<int>>& matrix, int target) {
    if (matrix.size() == 0 || matrix[0].size() == 0) {
        return false;
    }
        
    int y = 0;
    int x = matrix[0].size() - 1;

    while (y < matrix.size() && 0 <= x) {
     if (matrix[y][x] == target)
         return true;

     if (matrix[y][x] < target)
         ++y;
     else
         --x;
    }

    return false;
    }
};

解法3(二分探索)

この問題は二分探索を用いることでより効率的に解くことが可能です

時間計算量は$O(\log(n) + \log(m))$となります

空間計算量は再帰的なモデル, 反復的なモデルかによります

作者は個人的な理由で忙しいのでここではアイデアだけを述べます

行列の0列目の要素から二分探索を用いてtarget以上の要素の下界とtarget以下の要素の上界を求めます.

そして, その間の行で二分探索をして目的の要素があるかどうかを探します