剑指offer -二维数组中的查找 - python
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了剑指offer -二维数组中的查找 - python,小编现在分享给大家,供广大互联网技能从业者学习和参考。文章包含1602字,纯文字阅读大概需要3分钟。
内容图文
题目描述:
在一个二维数组中(每个一维数组的长度相同),每一行都按照从左到右递增的顺序排序,每一列都按照从上到下递增的顺序排序。请完成一个函数,输入这样的一个二维数组和一个整数,判断数组中是否含有该整数。
思路:
- 暴力求解法:由于数组中的元素是按规律存放的,对于xi,j?来说有xi?1,j?<xi,j?<xi+1,j?和xx,j?1?<xi,j?<xx,j+1?。所以,当数组的维度较低时,一种暴力的方法便是逐个的对比来查找数组中是否存在该整数。
- 聪明法:由于存在某种规律,所以我们可以从最小的元素所在的位置或是最大的元素所在的位置,即二维数组的左下角或是右上角开始查找。若当前位置的元素小于查找的数时,行数加1;否则列数加1.
AC代码
暴力求解法
# -*- coding:utf-8 -*-
class Solution:
# array 二维列表
def Find(self, target, array):
data = array[0]
# 全部元素
for i in range(1, len(array)):
data.extend(array[i])
if target in data:
return True
return False
聪明法
# 下三角寻找
# -*- coding:utf-8 -*-
class Solution:
# array 二维列表
def Find(self, target, array):
# write code here
if array == None:
return None
# 行数和列数
rows, cols = len(array), len(array[0])
# 下三角寻找
row = rows - 1
col = 0
while row >= 0 and col <= cols - 1:
if array[row][col] == target:
return True
elif array[row][col] > target:
row -= 1
else:
col += 1
return False
# 上三角寻找
# -*- coding:utf-8 -*-
class Solution:
def Find(self, target, array):
# write code here
if array == None:
return None
# 行数和列数
rows, cols = len(array), len(array[0])
col = cols - 1
row = 0
while col >= 0 and row <= rows - 1:
if array[row][col] == target:
return True
elif array[row][col] > target:
col -= 1
else:
row += 1
return False
内容总结
以上是互联网集市为您收集整理的剑指offer -二维数组中的查找 - python全部内容,希望文章能够帮你解决剑指offer -二维数组中的查找 - python所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错,欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明:本文内容由互联网用户自发贡献,该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 gblab@vip.qq.com 举报,一经查实,本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。