Javaアルゴリズム-2 DマトリクスIIの検索
1168 ワード
今日lintCodeで1つの問題をして、とても簡単で、しかし問題を解く構想はあまりにも巧みで、記録する必要があると感じます!
1.概要
(1).題意
効率的なアルゴリズムを書いてmを検索する×nマトリクスの値は、この値が現れる回数を返します.この行列は、各行の整数が左から右にソートされるという特性を有する.各カラムの整数は、上から下までソートされます.各行または列に重複する整数はありません.
(2).サンプル
次の行列を考慮します.
はtarget=3を与え、2を返す
(3).チャレンジ
はO(m+n)時間の複雑さとO(1)余分な空間を要求する
2.問題の解き方
この問題もとても簡単です.まず,配列の左下から遍歴する.現在の数字がtargetより大きい場合は、上が下より小さいため、上に移動します.現在の数字がtargetより小さい場合は、右が左より大きいため、右に移動します.現在の数字がtargetに等しい場合、sum++は右上の数字がtargetに等しい可能性があるため、右に移動します.
3.コード
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;
}