LeetCoding Challenge Oct. 16: Search a 2D Matrix

LeetCode October Challenge の 16 日目。

今日の問題は Search a 2D Matrix。

問題の概要

• 与えられた二次元配列上に target の値と等しい要素を探し出し、存在すれば true、存在しなければ false を返す
  • この二次元配列は左から右に向かって値が昇順に並んでおり、またある行の先頭の値はその前 (ひとつ上) の行の末尾の値より大きいという特性がある

考え方

• 二次元配列の特性から、以下のように配列を走査すれば O(w + h) (w は二次元配列の横幅、h は縦幅) の時間計算量で探し出せるね！
  1. 行を上から下に走査し、各行の先頭の値が target を超えない最も大きい値を持つ行を探し出す
  2. その行を今度は左から右に向かって、target を超える値に達するまで走査する
• でも、これを二次元配列ではなく一次元配列に見立てて二分探索した方が速いのでは？
  • 計算量は O(log(w * h)) になるね
• 実装してみよう → submit して accept 👏
  • Runtime は 0ms 👍

コード

class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        int height = matrix.length;
        if (height == 0) {
            return false;
        }

        int width = matrix[0].length;
        if (width == 0) {
            return false;
        }

        int size = width * height;

        int left = 0, right = size - 1;
        while (left <= right) {
            int mid = (left + right) >>> 1;
            int midRow = mid / width;
            int midCol = mid % width;

            int val = matrix[midRow][midCol];
            if (val == target) {
                return true;
            }
            if (val < target) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }

        return false;
    }
}