Leetcode Answers 240

依然是继续刷题,然而Leetcode上的题能刷的越来越少,设计题越来越多了。今天第一道题是搜索2D-Matrix。

题目:
Write an efficient algorithm that searches for a value in an m x n matrix. This 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.
    For example,

Consider the following matrix:

1
2
3
4
5
6
7
[
[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]
]

Given target = 5, return true.

Given target = 20, return false.

思路:
一个Sorted 2D-Matrix,要求Efficient,那也就是不能一次只看一边,要同时走row和col,既然每一行和每一列都已经是sorted了,这个实现起来就相对轻松了。

Answer:

1
2
3
4
5
6
7
8
9
10
11
12
13
public class Solution {
public bool SearchMatrix(int[,] matrix, int target) {
int currentRow = 0, currentCol = matrix.GetLength(1)-1;
while(currentRow<matrix.GetLength(0) && currentCol >= 0){
if(matrix[currentRow, currentCol] == target) return true;
else if(matrix[currentRow, currentCol] < target) currentRow++;
else if(matrix[currentRow, currentCol] > target) currentCol--;
}
return false;
}
}

考察:这道题的特殊点在于每一行每一列都是sorted,所以才可以如此用。其实我想到了另一个方法是特别复杂的,因为刚刚看了Interval Tree和Segment Tree,在想这个题里的Matrix是不是可以构建成Interval Tree,然后发现不对。。。

以上。

17-04-26
@Sturbridge