Javaアルゴリズム-2 DマトリクスIIの検索

1168 ワード

今日lintCodeで1つの問題をして、とても簡単で、しかし問題を解く構想はあまりにも巧みで、記録する必要があると感じます!
1.概要
(1).題意
効率的なアルゴリズムを書いてmを検索する×nマトリクスの値は、この値が現れる回数を返します.この行列は、各行の整数が左から右にソートされるという特性を有する.各カラムの整数は、上から下までソートされます.各行または列に重複する整数はありません.
(2).サンプル
次の行列を考慮します.
[
    [1, 3, 5, 7],
    [2, 4, 7, 8],
    [3, 5, 9, 10]
]

  はtarget=3を与え、2を返す
(3).チャレンジ
  はO(m+n)時間の複雑さとO(1)余分な空間を要求する
2.問題の解き方
この問題もとても簡単です.まず,配列の左下から遍歴する.現在の数字がtargetより大きい場合は、上が下より小さいため、上に移動します.現在の数字がtargetより小さい場合は、右が左より大きいため、右に移動します.現在の数字がtargetに等しい場合、sum++は右上の数字がtargetに等しい可能性があるため、右に移動します.
3.コード
    public int searchMatrix(int[][] matrix, int target) {
        if(matrix.length == 0 || matrix[0][0] > target) {
            return 0;
        }
        int sum = 0;
        int x = 0;
        int y = matrix.length - 1;
        while(x < matrix[0].length && y >= 0) {
            if(matrix[y][x] == target) {
                sum++;
                x++;
                y--;
            }else if(matrix[y][x] > target) {
                y--;
            }else {
                x++;
            }
        }
        return sum;
    }