[已解决]搜索二维矩阵问题(searchMatrix)

哲子DZ

题目是在矩阵中搜索target，有返回True，没有返回False，矩阵有两个特征每行中的整数从小到大排序的；每行的第一个数大于上一行的最后一个整数。

1. class Solution:
   
2. 
   
3.     def searchMatrix(self, matrix, target):
   
4.         if len(matrix) == 0:
   
5.             return False
   
6.             
   
7.         n, m = len(matrix), len(matrix[0])
   
8.         start, end = 0, n * m - 1
   
9.         while start + 1 < end:
   
10.             mid = (start + end) / 2
    
11.             x, y = mid / m, mid % m
    
12.             if matrix[x][y] < target:
    
13.                 start = mid
    
14.             else:
    
15.                 end = mid
    
16.         x, y = start / m, start % m
    
17.         if matrix[x][y] == target:
    
18.             return True
    
19.         
    
20.         x, y = end / m, end % m
    
21.         if matrix[x][y] == target:
    
22.             return True
    
23.         
    
24.         return False

复制代码

我一开始的思路是从矩阵右上角开始搜索，小于target可以过滤一行，大于的话可以过滤一列，但是也只是思路，到代码实现就完全不会了。以上代码是答案，按照答案的思路，第一个开始的元素是[1][3]，问题1：为什么从第2行最后一个元素开始？问题2：x，y的选择代码(x, y = mid / m, mid % m)是什么思路？非常感谢！！辛苦~

P.S.之所以说是第一个开始的元素是[1][3]，是因为有数据例子：[
  [1, 3, 5, 7],
  [10, 11, 16, 20],
  [23, 30, 34, 50]
]
target = 3， return True

最佳答案

月排行榜 / 总排行榜

shuofxz

2017-8-26 21:23:21

主体思路——二分法
把你这个矩阵展开成一行，第一行的末尾连第二行的开头，以此类推
选这个队列中的中间那个数和target比，相等就输出，若小可排除掉后面那一半数，若大同理
之后在对剩下的一半数重复上面的过程

这样寻找的效率要比的方法快一些，二分法也是在查找问题中非常常用的方法

第一个开始的元素是[1][3]   ->  你算的不对吧，如果行列的角标都从0开始，第一个元素是[1][1]正好是这一列数中间的那个数

x，y的选择代码(x, y = mid / m, mid % m)   ->    mid是这一列数中第几个数，还要把这个折合成矩阵的角标才行。
比如你的例子中求第一个数的时候 start = 0,  end = 11,  mid = (start+end)//2 = 5
x=mid//m=1   y=mid%m=1    (m=4)

你这个例子的答案应该是python2的吧，如果你的编译器是python3的话，要注意求x y的时候要用地板除//

跳转到最佳答案楼层

shuofxz

主体思路——二分法
把你这个矩阵展开成一行，第一行的末尾连第二行的开头，以此类推
选这个队列中的中间那个数和target比，相等就输出，若小可排除掉后面那一半数，若大同理
之后在对剩下的一半数重复上面的过程

这样寻找的效率要比的方法快一些，二分法也是在查找问题中非常常用的方法

第一个开始的元素是[1][3]   ->  你算的不对吧，如果行列的角标都从0开始，第一个元素是[1][1]正好是这一列数中间的那个数

x，y的选择代码(x, y = mid / m, mid % m)   ->    mid是这一列数中第几个数，还要把这个折合成矩阵的角标才行。
比如你的例子中求第一个数的时候 start = 0,  end = 11,  mid = (start+end)//2 = 5
x=mid//m=1   y=mid%m=1    (m=4)

你这个例子的答案应该是python2的吧，如果你的编译器是python3的话，要注意求x y的时候要用地板除//

哲子DZ

shuofxz 发表于 2017-8-26 21:23
主体思路——二分法
把你这个矩阵展开成一行，第一行的末尾连第二行的开头，以此类推
选这个队列中的中间 ...

看了您的解答，瞬间明白了啊！想不通的问题想通了的感觉实在是太好了啊！！谢谢！谢谢！！特别是“把你这个矩阵展开成一行”茅塞顿开啊，把矩阵转化成一维数组，不就是更简单的问题了嘛！然后自己写了代码，AC通过了！太兴奋了，谢谢，谢谢！！
以下是我的代码

1. class Solution:
   
2.     """
   
3.     @param matrix, a list of lists of integers
   
4.     @param target, an integer
   
5.     @return a boolean, indicate whether matrix contains target
   
6.     """
   
7.     def searchMatrix(self, matrix, target):
   
8.         # write your code here
   
9.         if len(matrix) == 0:
   
10.             return False
    
11.         temp_list = []
    
12.         for each_line in matrix:
    
13.             for each_element in each_line:
    
14.                 temp_list.append(each_element)
    
15.         start, end = 0, len(temp_list) - 1
    
16.         while start + 1 < end:
    
17.             mid = start + (end - start) / 2
    
18.             if temp_list[mid] == target:
    
19.                 return True
    
20.             elif temp_list[mid] < target:
    
21.                 start = mid
    
22.             else:
    
23.                 end = mid
    
24.         if temp_list[start] == target:
    
25.             return True
    
26.         elif temp_list[end] == target:
    
27.             return True
    
28.         return False

复制代码