2 DマトリックスIIを探す

これは一連のleetcode解決説明の一部です.あなたがこの解決が好きであるか、それが役に立つとわかるならば、このポストとmy solution post on Leetcode's forums .

2次元マトリックスIIを検索する

説明

にジャンプします.Solution Idea || コードJavaScript | Python | Java | C++ )

Write an efficient algorithm that searches for a target value in an m x n integer matrix. The matrix has the following properties:

• Integers in each row are sorted in ascending from left to right.
• Integers in each column are sorted in ascending from top to bottom.

例:

Example 1:
Input:	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
Output:	true
Visual:

Example 2:
Input:	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
Output:	false
Visual:

制約

• m == matrix.length
• n == matrix[i].length
• 1 <= n, m <= 300
• -10^9 <= matix[i][j] <= 10^9
• All the integers in each row are sorted in ascending order.
• All the integers in each column are sorted in ascending order.
• -10^9 <= target <= 10^9

考え

にジャンプします.Problem Description || コードJavaScript | Python | Java | C++ )
ここでのnaiveアプローチはo(m＊n)の時間複雑さですべてのセルをチェックすることである.これの明白な改善はO(M * log n)にこれを短くするために各行にバイナリ検索を使用することです.しかし、行列(M)が行と列の両方でソートされているので、実際には、各セル(m [ i ][ j ])は、現在のセルの下にあるだけでなく、左側のすべてのセルを含む、長い“行”の中点であると考えられる.
Mの右上隅から始めて、これを変更されたバイナリ検索のように扱うと、セルをチェックするたびに、行全体または列全体を削除できます.

それから、私たちのIまたはJ値を調整する必要があります.

これはo ( m + n )に時間の複雑さを落とすでしょう.
(注:左下隅から始めるときだけでなく動作します)

実装

Java以外のすべての場合には、jの境界条件をチェックするためにビット単位NOT演算子(~)を使用することができます.
(注:テストスイートでデザイン欠陥を利用することによって「より速い」結果を達成している一部の人々は、テストが同じマトリックス入力の1つ以上のループを含んでいるように見えます、そして、人々は答えを返す前に行列をクリアするという考えがありました.そして、それは、残りのループが処理するのを容易にするでしょう、突然変異された行列がテストのその後の反復で使用されるので).

JavaScriptコード

にジャンプします.Problem Description || Solution Idea )

var searchMatrix = function(M, T) {
    let y = M.length, i = 0, j = M[0].length - 1
    while (i < y && ~j) {
        let cell = M[i][j]
        if (cell === T) return true
        else if (cell > T) j--
        else i++
    }
    return false
};

Pythonコード:

にジャンプします.Problem Description || Solution Idea )

class Solution:
    def searchMatrix(self, M: List[List[int]], T: int) -> bool:
        y, i, j = len(M), 0, len(M[0]) - 1
        while i < y and ~j:
            cell = M[i][j]
            if cell == T: return True
            elif cell > T: j -= 1
            else: i += 1
        return False

Javaコード:

にジャンプします.Problem Description || Solution Idea )

class Solution {
    public boolean searchMatrix(int[][] M, int T) {
        int y = M.length, i = 0, j = M[0].length - 1;
        while (i < y && j >= 0) {
            int cell = M[i][j];
            if (cell == T) return true;
            else if (cell > T) j--;
            else i++;
        }
        return false;
    }
}

C ++コード:

にジャンプします.Problem Description || Solution Idea )

class Solution {
public:
    bool searchMatrix(vector<vector<int>>& M, int T) {
        int y = M.size(), i = 0, j = M[0].size() - 1;
        while (i < y && ~j) {
            int cell = M[i][j];
            if (cell == T) return true;
            else if (cell > T) j--;
            else i++;
        }
        return false;
    }
};