首页 > 试题广场 > 二维数组中的查找
[编程题]二维数组中的查找
在一个二维数组中(每个一维数组的长度相同),每一行都按照从左到右递增的顺序排序,每一列都按照从上到下递增的顺序排序。请完成一个函数,输入这样的一个二维数组和一个整数,判断数组中是否含有该整数。

133个回答

添加回答
推荐
/* 思路
* 矩阵是有序的,从左下角来看,向上数字递减,向右数字递增,
* 因此从左下角开始查找,当要查找数字比左下角数字大时。右移
* 要查找数字比左下角数字小时,上移
*/

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 回复(186)
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)
class Solution:
    # array 二维列表
    def Find(self, target, array):
        # write code here
        n = len(array)
        m = len(array[0])
        i = n - 1
        j = 0
        while i >= 0 and j<= m - 1:
            if target < array[i][j]:
                i -= 1
            elif target > array[i][j]:
                j += 1
            else :
                return True
        return False
  第一步:定义:两个变量 指代数组的行数n和列数m
  第二步:定义:两个变量 指代起始点的行号i和列号j
  第三步:设置 while 循环条件  (i 递减,j 递增)
  第四步: 循环体 元素判等和比较(<,>,=)
  第五步:循环终止,返回False
发表于 2019-03-28 11:24:50 回复(0)
想到的有两种方法,第一种是暴力遍历,也是最简单的:
class Solution(object):
  • # array 二维列表
  • def Find(self, target, array):
    • for i in array:
      • for j in i:
        • if j == target:
          • return True
第二种是根据二维数组排列的特点,利用左下角的数字的特殊性,跟左下角的数字比较,如果比它大,就往右查找,如果小,就往上面一行查找:
class Solution(object):
  • # array 二维列表
  • def Find(self, target, array):
    • rows = len(array) - 1
    • cols = len(array[0]) - 1
    • i = rows
    • j = 0
    • while j <= cols and i >=0:
      • if target < array[i][j]:
        • i -= 1
      • elif target > array[i][j]:
        • j += 1
      • else:
        • return True
      • return False

发表于 2019-03-27 22:14:49 回复(0)
# -*- coding:utf-8 -*-
class Solution:
    def Find(self, target, array):
        for i in array:
            if target in i:return True
Python了解一下~
发表于 2019-03-24 21:41:28 回复(1)
# -*- coding:utf-8 -*-
class Solution:
    def Find(self, target, array):
        i = 0 # 第一行,小于len(array)都可循环
        j = len(array[0]) - 1 # 最后一列,大于等于0都可循环
        while i < len(array) and j >= 0:
            aim = array[i][j] # 右上角的数
            if target < aim:
                j -= 1
            elif target > aim:
                i += 1
            else:
                return True
        return False
发表于 2019-03-23 22:33:53 回复(0)
从左下角开始搜索
class Solution:
    # array 二维列表
    def Find(self, target, array):
        # write code here
        row=len(array)-1
        col=0
        while row>=0 and col<=len(array[0])-1:
            if target==array[row][col]:
                return True
            elif target > array[row][col]:
                col+=1
            else:
                row-=1
        return False

发表于 2019-03-21 22:24:08 回复(0)
# -*- coding:utf-8 -*-
class Solution:
    # array 二维列表
    def Find(self, target, array):
        # write code here
        r = len(array)
        l = len(array[0])
        a = r-1
        b = 0
        while a>=0 and b<l:
            if target == array[a][b]:
                return True
            if target < array[a][b]:
                a = a-1
            if target > array[a][b]:
                b = b+1
        return False

发表于 2019-03-21 11:10:25 回复(0)
def find(target,array):
    row=len(array)-1
    col=0
    while (row>=0 and col<=len(array[0])-1):
        if target==array[row][col]:
            return True
        elif target>array[row][col]:
            col+=1
        elif target<array[row][col]:
            row-=1
    return False
数组向上减小,向右增大。以此规则可以遍历整个数组(从左下方开始搜索)
发表于 2019-03-21 04:02:58 回复(0)

一、给出的是方阵

[[1,6,7,8],

[3,7,8,9],

[9,10,11,12],

[12,13,14,15]]

这种情况非常简单,可知对角线元素应为查找元素,如果target大于对角线上某个元素,那么以此对角线为中心,左边、上边的元素应该都小于target

此时只需要找到一个对角线上的点,当找个一个刚刚好大于target的元素,那么左边和上边进行二分查找即可,python代码如下:


# -*- coding:utf-8 -*-
class Solution:
    # array 二维列表
    def Find(self, target, array):
        # write code here
        h, w = len(array), len(array[0])
        for i in range(min(h, w)):      # 在正方形内对角线查找
            if array[i][i] == target:
                return True
            elif (array[i][i] > target):
                for j in range(i):        # 这里可以替换成二分查找
                    if (array[i][j] == target or array[j][i] == target):
                        return True
            return False 

考虑到非方阵情况例如

[[1,6,7,8],

[3,7,8,9],

[9,10,11,12],

[12,13,14,15],

[13,14,15,16],

[,18,21,22,23]]

其中array的shape=(6,4)
这时候就不能单一按照对角线考虑,应该将矩阵分块,分成多个小方阵,利用递归的方式现将矩阵分块,然后每一个小方阵按照上述对角线方式查找,python代码如下
# -*- coding:utf-8 -*-
class Solution:
    # array 二维列表
    def Find(self, target, array):
        # write code here
        h, w = len(array), len(array[0])
        if (h==0 or w==0):                
                  # 递归退出条件,当矩阵不可再分时候,此时为行向量,顺序查找或者二分查找
            for i in range(max(h,w)):
                if(target == array[i]):
                    return True
            return False
           # 如果按照方阵情况查找
        for i in range(min(h, w)):      # 在正方形内对角线查找
            if array[i][i] == target:
                return True
            elif (array[i][i] > target):
                for j in range(i):        # 这里可以查找二分查找
                    if (array[i][j] == target or array[j][i] == target):
                        return True
        if (h > w):    # 如果不是方阵,则递归划分成多个小方阵查找
            return self.Find(target, [row[:w] for row in array[i+1:]])
        else:
            return self.Find(target, [row[i+1:] for row in array[:h]])

编辑于 2019-03-18 15:47:07 回复(0)

从右上角开始判断,如果比当前点小,那么一定在当前点的左边,如果大,那么一定在当前点的下边。如果从左上角开始判断同一行同一列的值仍会干扰判断

# -*- coding:utf-8 -*-
class Solution:
    # array 二维列表
    def Find(self, target, array):
        # write code here
        row = len(array)
        col = len(array[0])
        i = row -1
        j = 0
        while i > 0 and j < col:
            if array[i][j] == target:
                return True
            elif array[i][j] > target:
                i -= 1
            else:
                j += 1
        return False
发表于 2019-03-12 11:17:04 回复(0)
思路:
1.如果array数组为空,就返回False,如果数组array[0]为空,返回False
2.开始从右上角遍历数组,
如果target等于当前值,返回True,
如果target大于当前值,说明当前值所在列全都大于target,所以排出掉这一列,在剩下的矩阵中寻找target,
如果target小于当前值,说明当前值所在行全部小于target,所以排出掉这一行,在剩下的矩阵中寻找target,

代码:
	
# -*- coding:utf-8 -*-
class Solution:     # array 二维列表     def Find(self, target, array):         # write code here         if not array or not array[0]:             return False         row = len(array)         col = len(array[0])                  i = 0         j = col - 1                  while i <= row - 1 or j >= 0:                          if array[i][j] == target:                 return True             elif array[i][j] > target and j > 0:                 j -= 1             elif array[i][j] < target and i < row - 1:                 i += 1             else:                 return False

发表于 2019-03-11 22:56:17 回复(0)
java太复杂啦 ,看我python
class Solution:
    # array 二维列表
    def Find(self, target, array):
        # write code here
        for i in range(len(array)):
            if target in array[i]:
                return True
        return False

发表于 2019-03-11 14:33:25 回复(0)
# -*- coding:utf-8 -*-
class Solution:
    # array 二维列表
    def Find(self, target, array):
        col=len(array)-1
        row=0
        while col>=0 and row < len(array[col]):
            if target == array[row][col]:
                return True
            elif target > array[row][col]:
                row+=1
            else:
                col-=1
        return False

发表于 2019-03-08 20:47:19 回复(0)
class Solution:
    # array 二维列表
    def Find(self, target, array):
        if len(array) ==False or len(array[0]) == False:
            return False
        rows = len(array) - 1
        cols = len(array[0]) -1
        i = rows
        j = 0
        while i >=0 and j<=rows:
            if target < array[i][j]:
                i = i - 1
            elif target > array[i][j]:
                j = j + 1
            elif target == array[i][j]:
                return True
        return False

从左下角查起,往上查小,往右查大,len([]) == False
发表于 2019-03-07 16:41:46 回复(0)