首页 > 试题广场 > 二维数组中的查找
[编程题]二维数组中的查找
在一个二维数组中(每个一维数组的长度相同),每一行都按照从左到右递增的顺序排序,每一列都按照从上到下递增的顺序排序。请完成一个函数,输入这样的一个二维数组和一个整数,判断数组中是否含有该整数。
推荐
/* 思路
* 矩阵是有序的,从左下角来看,向上数字递减,向右数字递增,
* 因此从左下角开始查找,当要查找数字比左下角数字大时。右移
* 要查找数字比左下角数字小时,上移
*/

class Solution {
public:
    bool Find(vector<vector<int> > array,int target) {
        int rowCount = array.size();
        int colCount = array[0].size();
        int i,j;
        for(i=rowCount-1,j=0;i>=0&&j<colCount;)
        {
            if(target == array[i][j])
                return true;
            if(target < array[i][j])
            {
                i--;
                continue;
            }
            if(target > array[i][j])
            {
                j++;
                continue;
            }
        }
        return false;
    }
};

编辑于 2015-06-18 16:50:07 回复(199)
# -*- coding:utf-8 -*-
class Solution:
    # array 二维列表
    def Find(self, target, array):
        # write code here
        self.target=target
        self.array=array
        n=len(self.array)
        m=len(self.array[0])
        flag=False
        if (len(self.array[0]) == 0):
            return False
        if(self.target<self.array[0][0]) or (self.target>self.array[n-1][m-1]):
            return False
        for i in range(0,n):
            l=0
            r=n-1
            while(l<=r):
                mid=(l+r)//2
                if(self.target<array[i][mid]):
                    r=mid-1
                elif(self.target>array[i][mid]):
                    l=mid+1
                else:
                    return True
        return False
发表于 2019-07-17 17:01:37 回复(0)
该二维数组中的一个数,他的左面的数都比它小,下面的数都比它大,因此,从右上角开始查找,就可以根据target和当前元素的大小关系来缩小查找的区间,当前元素的查找区间为左下角的所有元素。
发表于 2019-07-17 15:53:07 回复(0)
class Solution:
    # array 二维列表
    def Find(self, target, array):
        # write code here
        row = 0  
        maxrow = len(array) - 1   
        col = len(array[0]) - 1  
        while col>=0 and row<= maxrow:  
            if array[row][col]  == target:  
                return True  
            elif  target > array[row][col]:  
                row+=1  
            else :  
                target < array[row][col]  
                col-=1  
        return False  
运行结果
运行时间:336ms

占用内存:5708k

解决思路:
 从右上角进行查找,判断目标和数组值大小关系
如目标值大于数组值,则行数+1
反之则说明目标值在第一行,列数-1
当所有遍历结束后,返回false

发表于 2019-07-16 15:19:19 回复(0)
# -*- coding:utf-8 -*-
class Solution:
    # array 二维列表
    def Find(self, target, array):
        # write code here
        row = len(array)
        col = len(array[0])
        i, j = 0, col-1
        while i < row and j >= 0:
            if array[i][j] == target:
                return True
            elif array[i][j] < target:
                i += 1
            else:
                j -= 1
        return False
        '''
        while True:
            if len(array[0]) >= 1 and len(array) >= 1:
                this = array[-1][0] 
            else:
                return False
            if this == target: 
                return True
            elif target > this and len(array[0]) > 1:
                array = [a[1:] for a in array]  
            elif target < this and len(array) > 1:
                array = array[:-1] 
            else: 
                return False
        '''
发表于 2019-07-07 10:22:39 回复(0)
class Solution:
    # array 二维列表
    def Find(self, target, array):
        # write code here
        return bool(filter(lambda arr: target in arr, array))

发表于 2019-07-04 15:10:07 回复(0)
class Solution:
    # array 二维列表
    def Find(self, target, array):
        rows = len(array)
        cols= len(array[0])
        i = 0
        j = cols - 1
        while i<=rows and j>=0:
            if target<array[i][j]:
                j -= 1
            elif target>array[i][j]:
                i += 1
            else:
                return True
        return False

答案错误:您提交的程序没有通过所有的测试用例
case通过率为35.29%
为啥显示越界了啊

发表于 2019-07-02 19:51:28 回复(0)
python 思路:
设数组大小为(m,n)
判断数组右上角元素与目标元素的大小,
如果大于右上角元素(1,n),
则对比(2,n),
否则对比元素(1,n-1).
以此类推直到索引越界。

    def Find(self, target, array):
        # write code here
        rows = len(array) - 1
        cols = len(array[0]) - 1
        i,j = 0,cols
        while rows >= i and j >= 0:
            if target > array[i][j]:
                i += 1
            elif target < array[i][j]:
                j -= 1
            else:
                return True
        return False
编辑于 2019-06-23 20:01:42 回复(0)
# -*- coding:utf-8 -*-
class Solution:
    def Find(self, target, array):
        num = len(array)
        for i in range(len(array)):
            if target in array[i]:
                return True
            elif i == num:
                return False
虽然侥幸通过测试,但是还用许多值得提高的地方。
我的思路很简单,只遍历行,如果遇到所求数字在当前行就返回true,当到最后一行时返回false。
并没有做什么空列表检测,感觉还是不完整吧。
刚才看了许多高分解决方案,觉得自己的想法太简单太天真了,做遍历的时候许多行是不用遍历的,所以浪费了许多系统资源,看到他们说从左下角或者右上角逐个比对,感觉好厉害
编辑于 2019-06-23 16:58:10 回复(0)
利用有序的行列
先对角查询
后对角之间寻找

# -*- coding:utf-8 -*-
class Solution:
    def Find(self, integer, array):
        select_i = 0
        row_len = len(array[0])
        col_len = len(array)
        flag = False
        for i in range(row_len if row_len<col_len else col_len):
            if array[i][i] == integer:
                flag = True
                break
            elif integer < array[i][i]:
                if integer in array[i] or integer in array[i-1]:
                    flag = True
                    break
        return flag

发表于 2019-06-13 16:46:51 回复(0)
# -*- coding:utf-8 -*-
class Solution:
    # array 二维列表
    def Find(self, target, array):
        for ar in array:
            try:
                ar.index(target)
                return True
            except Exception as e:
                pass
        return False
python大法好

发表于 2019-06-03 19:21:26 回复(0)
解析:
step 1: 查看矩阵是否为空,不要用len 或者 not ,用 == [ [ ] ],因为len([[]]) = 1。空则返回False
非空,step 2
step 2: 因为从左到右,从上到下都有序,查看矩阵第一个数a(最小值), 最后一个数b(最大值arrary[-1][-1]), 若 target < a or target >b
返回False,   否则,step 3
step 3:for 遍历每一行,如果该行的末位数array[i][-1] continue ,进入下一行,否则,step 4
step 4: 对该行进行二分查找,找到return True
最终
未找到,return False

# -*- coding:utf-8 -*-
class Solution:
    # array 二维列表
    def Find(self, target, array):
        # write code here
        if array == [[]]:
            return False
        if target < array[0][0] or target > array[-1][-1]:
            return False
        len_row = len(array)
        len_col = len(array[0])
        for i in range(len_row):
            if array[i][-1] < target:
                continue
            else:
                left = 0
                right = len_col
                while left < right:
                    mid = (left + right)//2
                    if target == array[i][mid]:
                        return True
                    elif target < array[i][mid]:
                        right = mid
                    else:
                        left = mid + 1
        return False

发表于 2019-05-30 22:27:54 回复(0)
#参考排名第一的思路,用python写了下
# -*- coding:utf-8 -*-
class Solution:
    # array 二维列表
    def Find(self, target, array):
        # write code here
        # 左下角
        '''
        * 矩阵是有序的,从左下角来看,向上数字递减,向右数字递增,

        * 因此从左下角开始查找,当要查找数字比左下角数字大时。右移

        * 要查找数字比左下角数字小时,上移
        '''
        print(len(array))#  我擦嘞,len([[]])=1原来等于1
        if array and array[0]:
            i = len(array)-1
            jmax=len(array[0])

            j = 0
            flag = False
            # for i in range(array.shape[0]):
            while (i >= 0 and (i <len(array)) and (j >= 0) and (j < len(array[0]))):
                if target == array[i][j]:
                    flag = True
                    break
                elif target > array[i][j]:
                    j = j + 1
                else:
                    i = i - 1
                    '''
                if i<0 or j>=len(array[0]):
                    flag=False
                    break
                    '''
            return flag
        else:
            return False
发表于 2019-05-28 10:14:39 回复(0)
def Find(self, target, array):
    # write code here 
    i = 0
    height = len(array)
    if height == 0:
        return False
    width = len(array[0])
    ind_sum = width + height - 1
    while (i < ind_sum):
        for j in range(i+1):
            if j >= height:
                break
            elif i-j >=width:
                continue
            if array[j][i-j] == target:
                return True
        i += 1
    return False

语言:Python2 / 3

思路:每次检查矩阵斜线上的元素,index的加和从0递增,并判断边界。

算法速度:327 ms

占内存:5752K

编辑于 2019-05-07 10:06:38 回复(0)
# -*- coding:utf-8 -*-
class Solution:
    # array 二维列表
    def Find(self, target, array):
        # write code here
        row = 0
        col = len(array[0])-1
        while row < len(array) and col >= 0:
            if target > array[row][col]:
                row += 1
            elif target < array[row][col]:
                col -= 1
            else:
                return True
        return False

发表于 2019-04-22 14:53:13 回复(0)
# -*- coding:utf-8 -*-
class Solution:
    # array 二维列表
    def Find(self, target, array):
        # write code here
        for i in range(len(array[0])):
            for j in range(len(array[:][0])):
                if array[i][j] == target:
                    return True
                
        return False
渣渣方法
发表于 2019-04-15 22:07:28 回复(0)
递归算法+整体二分查找:
利用矩阵中心值将矩阵分为四部分,【左上】【左下】【右上】【右下】,
如果矩阵中心值大于target,递归查找【左上】【左下】【右上】,
如果矩阵中心值小于target,递归查找【右下】,如果相等,返回True。
递归终止条件:矩阵为规模为2*2或小于2*2
时间复杂度 logM*logN
class Solution:
    # array 二维列表
    def Find(self, target, array):
        if array==[[]]:return False
        def searchTarget(target,array,beginIndex,endIndex):
                      
            midIndex=map(int,[(beginIndex[0]+endIndex[0])/2.0,(beginIndex[1]+endIndex[1])/2.0])
            if beginIndex==midIndex:
                if array[beginIndex[0]][beginIndex[1]]==target or \
                   array[beginIndex[0]][endIndex[1]]==target or \
                   array[endIndex[0]][beginIndex[1]]==target or \
                   array[endIndex[0]][endIndex[1]]==target:
                    return True
                else:
                    return False
            else:
                xM,yM=midIndex
                x1,y1=beginIndex
                x2,y2=endIndex
                if array[xM][yM]>target:
                    result=searchTarget(target,array,beginIndex,midIndex)
                    if result==True:return result
                    result=searchTarget(target,array,[x1,yM],[xM,y2])
                    if result==True:return result
                    result=searchTarget(target,array,[xM,y1],[x2,yM])
                    if result==True:return result
                elif array[xM][yM]<target:
                    result=searchTarget(target,array,midIndex,endIndex)
                    if result==True:return result
                else:
                    return True
            return result
        
        return searchTarget(target,array,[0,0],[len(array)-1,len(array[0])-1])

编辑于 2019-04-15 16:28:33 回复(0)
# -*- coding:utf-8 -*-
class Solution:
    # array 二维列表
    def Find(self, target, array):
        # write code here
        row = len(array)
        col = len(array[0])
        if row == 0 or col == 0 or array[0][0] > target:
            return False
        
        for i in range(row):
            if array[i][0] == target:
                return True
            elif array[i][0] > target:
                row = i
                break
                
        for j in range(col):
            if array[0][j] == target:
                return True
            elif array[0][j] > target:
                col = j
                break
        
        if row == 1 or col == 1:
            return False
        
        array_new = array[1:row]
        for i in range(row-1):
            array_new[i] = array_new[i][1:col]
            
        sol = self.Find(target, array_new)
        return sol
看了答案才发觉从左下或右上查找是最好的,做的时候没想到,想到的是一种递归的思路。
分别遍历第一列和第一行,分别记下第一列中比target大的第一个数的行索引和第一行中比target大的第一个数的列索引,然后将超出的元素舍去,得到一个小矩阵,对这个小矩阵递归查找,只剩一行或一列时就是递归出口。
发表于 2019-04-11 16:18:10 回复(0)
从左上角开始横向遍历,当元素大于 target 时,该元素右下区域都不用再遍历
# -*- coding:utf-8 -*-
class Solution:
    # array 二维列表
    def Find(self, target, array):
        # write code here
        row_num = len(array)
        col_num = len(array[0])
        for i in range(row_num):
            if row_num == 0 or col_num == 0:
                return False
            for j in range(col_num):
                if array[i][j] == target:
                    return True
                elif array[i][j] < target:
                    continue
                else:
                    col_num = j
                    break
        return False

发表于 2019-03-30 18:29:11 回复(0)