python求解矩阵搜索问题,矩阵中每一行和第一列都是递增的-给定一个元素查找矩阵中是否存在该元素
目录
python求解矩阵搜索问题，矩阵中每一行和第一列都是递增的 给定一个元素查找矩阵中是否存在该元素
矩阵搜索问题，给定一个矩阵，矩阵中的而每一行都是递增的，第一列也是递增的，其余信息未知，给定一个元素查找矩阵中是否存在该元素，乍眼一看跟矩阵中行列都是递增的题目一样，其实不然，这里只有第一列是递增的其余都是不知道的，所以就不能按照行列都是递增的方法来做了
这里简单说一下自己的思路，如下这个矩阵：
1 3 15 17 19
2 4 16 17 22
3 4 21 44 51
6 7 18 29 36方法是：题目中说的是每行都是递增的，那么可以知道每行最后一个值是最大的，那么我先抽取出来每行最大值即最后一个值，之后遍历一次与给定的数字对比，找出比给定数字大的或者相等的行索引，这些是需要遍历判断的，其余的就不需要考虑了，暂时没理解第一列也是递增的是什么意思有什么用处，下面是具体实现：
#!usr/bin/env python
#encoding:utf-8
'''
__Author__:沂水寒城
功能：矩阵搜索问题，给定一个矩阵，矩阵中的而每一行都是递增的，第一列也是递增的
其余信息未知，给定一个元素查找矩阵中是否存在该元素
'''
def matrix_search(matrix, num):
'''
矩阵搜索
'''
last_col_list=[one_list[-1] for one_list in matrix]
index_list=[]
for i in range(len(last_col_list)):
if last_col_list[i]>=num:
index_list.append(i)
flag=False
res_list=[]
while index_list:
one_row=index_list.pop()
one_list=matrix[one_row]
if num in one_list:
tmp_str='Row:{0},Col:{1}'.format(one_row,one_list.index(num))
res_list.append(tmp_str)
flag=True
if flag:
print '{0} Exists in {1}'.format(num, res_list)
else:
print '{0} No Exists!'.format(num)
if __name__ == '__main__':
matrix=[[1,3,15,17,19],
[2,4,16,17,22],
[3,4,21,44,51],
[6,7,18,29,36]]
for i in range(4):
one_list=map(str, matrix[i])
print ' '.join(one_list)
num_list=[15,12,21,29,19]
for one_num in num_list:
matrix_search(matrix, one_num)结果如下：
1 3 15 17 19
2 4 16 17 22
3 4 21 44 51
6 7 18 29 36
15 Exists in ['Row:0,Col:2']
12 No Exists!
21 Exists in ['Row:2,Col:2']
29 Exists in ['Row:3,Col:3']
19 Exists in ['Row:0,Col:4']
[Finished in 0.3s]