首页 > 试题广场 >

二维数组中的查找

[编程题]二维数组中的查找

热度指数：2367328 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

在一个二维数组array中（每个一维数组的长度相同），每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。

[

[1,2,8,9],
[2,4,9,12],
[4,7,10,13],
[6,8,11,15]

]

给定 target = 7，返回 true。

给定 target = 3，返回 false。

数据范围：矩阵的长宽满足 $0 \le n,m \le 500$ ，矩阵中的值满足 $0 \le val \le 10^9$
进阶：空间复杂度 $O(1)$ ，时间复杂度 $O(n+m)$

示例1

输入

7,[[1,2,8,9],[2,4,9,12],[4,7,10,13],[6,8,11,15]]

输出

true

说明

存在7，返回true

示例2

输入

1,[[2]]

输出

false

示例3

输入

3,[[1,2,8,9],[2,4,9,12],[4,7,10,13],[6,8,11,15]]

输出

false

说明

不存在3，返回false

算法知识视频讲解

推荐

徘徊的路人甲

/* 思路

* 矩阵是有序的，从左下角来看，向上数字递减，向右数字递增，

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

* 要查找数字比左下角数字小时，上移

*/

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 回复(249)

Python

曰无衣bupt

用python写一个其实有点不符合题目考查的代码：

    def Find(self, target, array):
        # write code here
        if len(array)==0&nbs***bsp;len(array[0])==0:
            return 0
        # 直接用python行吗？
        for i in array:
            if target in i:
                return True
        return False

发表于 2022-06-15 18:18:48 回复(0)

Python

牛客113500610号

class Solution:
def Find(self, target, array):
for i in array:
if i:
if target > i[-1]:
continue
if target < i[0]:
return False
if target in i:
return True
return False

发表于 2021-04-18 08:16:26 回复(0)

Python

Or201809061041224

# -*- coding:utf-8 -*-
class Solution:
    # array 二维列表
    def Find(self, target, array):
        if any(array):
            t = [array[i][i] for i in range(min(len(array),len(array[0])))]
            i, isfind = self.FuzzyBS(target, t)
            if isfind:
                return True
            if self.Find(target, [row[:i] for row in array[i:]]):
                return True
            if self.Find(target, [row[i:] for row in array[:i]]):
                return True
        return False

    def FuzzyBS(self, target, vector):
        l = 0
        r = len(vector) - 1
        while r >= l:
            mid = (l + r) / 2
            if vector[mid] > target:
                r = mid - 1
            elif vector[mid] < target:
                l = mid + 1
            elif vector[mid] == target:
                return mid, True
        return l, False

首先二分查找主对角线上与target相等或比target大的第一个数

找到target则返回True

未找到target时，对矩阵进行十字分块，分别对右上和左下矩阵重复运行该算法

适用于非方阵

递归换成多线程方法，则可适用于对超大矩阵的并行查找

略加修改可用于查找矩阵中所有与target相等的元素的位置

发表于 2021-03-13 17:40:34 回复(0)

Python

牛客643031252号

这一道题和二分排序很像，需要注意的是array本身的规律，按照二分排序比大小选择目标的规律，可以从左下角开始，如果array[i][j]大于target则往上移动，小于则往右移动，需要注意不能越界。因此就是找规律二分排序二分排序二分排序！（在此

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

感谢知乎大佬半情调的分享，本回答仅作个人知识深化）

发表于 2021-03-13 09:22:54 回复(0)

Python

在下小6

python解法：
解法一：暴力法

# 解法1:暴力法
class Solution:
    # array 二维列表
    def Find(self, target, array):
        len1 = len(array)
        len2 = len(array[0])
        for i in range(len1):
            for j in range(len2):
                if array[i][j] == target:
                    return True
        return False

解法二：从右上角开始查找；

# 解法2:从右上角开始查找；
class Solution:
    # array 二维列表
    def Find(self, target, array):
        len1 = len(array) # 行
        len2 = len(array[0]) # 列
        if len1 == 0 or len2 == 0:
            return False
        r, c = 0, len2 - 1
        while r < len1 and c >= 0:
            if array[r][c] == target:
                return True
            # array[r][c]<target，左边和上边的都比现在的值小，所以只能向下移；
            elif array[r][c] < target:
                r += 1
            # array[r][c]>target，右边和下边的都比现在的值小，所以只能向左移；
            else:
                c -= 1
        return False

解法三：从左下角开始查找；

# 解法3:从左下角开始查找；
class Solution:
    # array 二维列表
    def Find(self, target, array):
        len1 = len(array) # 行
        len2 = len(array[0]) # 列
        if len1 == 0 or len2 == 0:
            return False
        r, c = len1 - 1, 0
        while r >= 0 and c < len2:
            if array[r][c] == target:
                return True
            # array[r][c]<target，左边和上边的都比现在的值小，所以只能向右移；
            elif array[r][c] < target:
                c += 1
            # array[r][c]>target，右边和下边的都比现在的值大，所以只能向上移；
            else:
                r -= 1
        return False

发表于 2021-02-18 18:28:01 回复(0)

Python

学习不能停下呀

# -*- coding:utf-8 -*-

#内层矩阵折半查找

class Solution:
def Find(self,target,array):
if len(array)==0 or len(array[0])==0:
return False
for x in array:
if x[0]<=target<=x[-1]:
lindex=0
rindex=len(x)-1
while lindex<=rindex:
mid=(lindex+rindex)/2
if x[mid]==target:
return True
if x[mid]>target:
rindex=mid-1
else:
lindex=mid+1
return False

发表于 2020-12-03 17:48:46 回复(0)

Python

12313242

从右上角出发。

class Solution:
    # array 二维列表
    def Find(self, target, array):
        # write code here
        ncol = len(array[0])
        nrow = len(array)
        x,y = 0, ncol-1
        while x<ncol and y>=0:
            if array[x][y] > target:
                y -= 1
            elif array[x][y] < target:
                x += 1
            else:
                return True
        return False

编辑于 2020-10-14 00:38:22 回复(0)

Python

wulinglin

我的答案运行时间：197ms; 占用内存5752KB

我能想到的是递归二分查找target。

首先根据从中间切成左上、右上、左下、右下四个块，令为1、2、3、4，然后再找这四个块是否有target。

复杂度logn*logn?

但是debug花了好久啊，容易出错的点在于：

1、这里的二维列表不是numpy数组，所以不能用数组切片的方式，要用list的切片

2、可能有target介于多个块中最大最小值之间，所以需要多个块都查找，而不是查找到一个就停止。

3、牛客网的debug好难啊，我只能本地debug！呜呜

以下是我的题解：

# -*- coding:utf-8 -*-
class Solution:
    # array 二维列表
    def Find(self, target, array):
        # write code here
        if len(array) == 0&nbs***bsp;len(array[0]) == 0&nbs***bsp;not array[0][0] <= target <= array[-1][-1]:
            return False
        if target == array[0][0]&nbs***bsp;target == array[-1][-1]:
            return True
        m, n = len(array), len(array[0])
        mid_m, mid_n = int(m / 2), int(n / 2)
        array_1 = [i[:mid_n] for i in array[:mid_m]]
        array_2 = [i[mid_n:] for i in array[:mid_m]]
        array_3 = [i[:mid_n] for i in array[mid_m:]]
        array_4 = [i[mid_n:] for i in array[mid_m:]]
        return self.Find(target, array_1)&nbs***bsp;self.Find(target, array_2)&nbs***bsp;self.Find(target, array_3)&nbs***bsp;self.Find(target, array_4)

编辑于 2020-09-19 21:36:43 回复(0)

Python

newcoderagain

请问为什么我的代码在编译器遇到“16,[[]]”就会显示“list index out of range”但是在本地可以通过。具体代码如下：

# -*- coding:utf-8 -*-
import sys

class Solution:
    # array 二维列表
    def Find(self, target, array):
        # write code here
        
        # get array size
        m=len(array)
        n=len(array[0])
        if m==0:
            return False
    
        isIncluded=False
        
        for i in range(m):
            if array[i][n-1]==target:
                #get the target
                isIncluded=True
                break
            elif array[i][n-1]<target:
                #not possible in this row
                continue
            elif array[i][0]>target:
                # the rest are larger numbers
                break
            
            #possibly in this row
            for j in range(n):
                if array[i][j]==target:
                    isIncluded=True
                elif array[i][j]>target:
                    #not in this row
                    break
                
                        
        return isIncluded

if __name__=="__main__":
    #read 
    line=sys.stdin.readline()
    line=list(eval(line))
    target=line[0]
    arr=line[1]
    
    if len(arr[0])==0:
        isEmptyArr=True
    else:
        isEmptyArr=False
            
    if isEmptyArr:
        print("false")
    else:
        solution=Solution()
        if solution.Find(target, arr):
            print("true")
        else:
            print("false")

发表于 2020-09-19 01:32:17 回复(0)

Python

BJ-2020

思路:
矩阵的最右上角(array[0][-1])的值与target作比较如果target大，删除右上角所在行，如果target小，则删除右上角所在列，相等则输出正确，边界条件假设到最左下角，也就是行数<最大列数,列数>=0

# -*- coding:utf-8 -*-
class Solution:
    # array 二维列表
    def Find(self, target, array):
        # write code here
        if array == None:
            return None
        # 递增数列
        i = 0
        j = len(array[0]) - 1
        while i < len(array) and j >= 0:
            value = array[i][j]

            if value == target:
                return True
            elif value < target:
                i += 1
            else: 
                j -= 1


        return False

发表于 2020-09-07 21:17:26 回复(0)

Python

LV52

class Solution:
    # array 二维列表
    def Find(self, target, array):
        m = len(array)
        find = 'false'
        for i in range(m):
            sub_array = array[i]
            first = 0
            last = len(sub_array) - 1

            while first <= last:
                mid_index = (first + last) // 2
                if sub_array[mid_index] < target:  # 往中间元素的右侧查找
                    first = mid_index + 1
                elif sub_array[mid_index] > target:
                    last = mid_index - 1
                else:
                    find = 'true'
                    break
        return find



c = Solution()
print(c.Find(input()[0],input()[1]))


我这样提交为什么用5,[[1,2,8,9],[2,4,9,12],[4,7,10,13],[6,8,11,15]]这个示例的时候不通过，我在本地编译器都是false，但是到了这里在线运行就变成true了，搞不懂

发表于 2020-08-20 10:42:16 回复(0)

Python

DDooo

# -*- coding:utf-8 -*-
class Solution:
    # array 二维列表
    def Find(self, target, array):
        # write code here
        # 1,2,3,4,5
        # 6,7,8,9,10
        # 11,12,13,14,15
        # 16,17,18,19,20
        rowNum = len(array)#4
        colNum = len(array[0])#5
        i = 0
        j = colNum - 1
        while i < rowNum and j >= 0:
            value = array[i][j]
            if target == value:
                return True
            elif target < value:
                j -= 1
            else :
                i += 1
        return False #None也可以

发表于 2020-07-28 19:18:16 回复(0)

Python

牛客720457535号

注意有特例的输入

array=[[]]

此时array[0][0]会报错list index out of range

编辑于 2020-07-21 11:09:37 回复(0)

Python

牛客279485353号

最高效最简洁的写法15行给你

分析题目：

明显是查找题。查找分两种，无规则无序查找（联想经典算法，根据复杂度和条件选择之一）和相对有序查找（本题）。相对有序查找一般要多分析排序规则。

本题规则特点：

左上右下，分别是最小和最大值。左下和右上呢？分别是最后一行最小值&第一列最大值和第一行最大值&最后一列最小值。由此，我们可以想象，从左下的点为current-point，如target > cur-point 则候选区域可以排除第一列，排除后新的矩阵左下为[2,N]。如target > cur-point则候选区域可排除最后一行，排除后新的矩阵左下为[1,N-1]。以此类推到停止条件。

思路：

由此，我们可以想象，从左下的点为current-point，如target > cur-point 则候选区域可以排除第一列，排除后新的矩阵左下为[2,N]。如target > cur-point则候选区域可排除最后一行，排除后新的矩阵左下为[1,N-1]。以此类推到停止条件。

    def Find( self, target, array):
    # write code here
        if len(array) == 0:
            return False
        High = len(array)
        Wigth = len(array[0])
        high = High -1
        wight = 0
        while high >= 0 and wight < Wigth:
            cur = array[high][wight]
            if target == cur:
                return True
            elif target > cur:
                wight = wight + 1
            else:
                high = high - 1
        return False

编辑于 2020-06-29 02:29:52 回复(0)

Python

M.WW

baoli思路：
先按行，看每行最后一个数字和target比较。比target小直接跳过，比target大再倒过来往前搜索这一行之前的数。

class Solution:
  # array 二维列表
  def Find(self, target, array):
      # write code here
      if len(array) ==  0 or len(array[0]) == 0:
          return False
      col = len(array[0]) - 1
      for i in range(len(array)):
          if target <= array[i][col]:
              for j in range(len(array[0])-1, -1, -1):
                  if target == array[i][j]:
                      return True
      return False

改进版，走一个对角线：O(N+M) = O(N),即 target只要比当前值小，他一定在下三角阵

row_count = len(array)
      col_count = len(array[0])
      i = 0
      j = col_count - 1
      while i < row_count and j >= 0:
          value = array[i][j]
          if value == target:
              return True
          elif target < value:
              j -= 1
          else:
              i += 1
      return False

编辑于 2020-06-20 04:51:23 回复(0)

Python

牛客624277366号

# -*- coding:utf-8 -*-
class Solution:
    # array 二维列表
    def Find(self, target, array):
        # write code here
        c = []
        for i in array:
            print(i)
            if target in i:
                c.append(1)
            else:
                c.append(0)
        if 1 in c:
            return True
        else:
            return False

发表于 2020-06-01 15:48:08 回复(0)

Python

橘子汽水超人2号

    def Find(self, target, array):
        # write code here
        return any(target in x for x in array)

Python Solution

编辑于 2020-05-30 12:19:50 回复(0)

Python

牛客62019939号

# -*- coding:utf-8 -*-
from multiprocessing import Process, Queue
from signal import *
from time import time
import sys

value = None
q = Queue()

class Solution:
def __init__(self, target, array):
self.jobs = []
self.target = target
self.array = array

def Find(self, num):
# write code here
if self.array in self.target[num]:
q.put(True)
# return True
# else:
# return False
# sys.exit("array在target中")
# else:
# print("array不在target中")

def my_process(self):
number = len(self.target)
for i in range(number):
if self.array >= self.target[i][0]:
p = Process(target=self.Find, args=(i,))
self.jobs.append(p) # 进程对象
p.daemon = True # 主进程退出，其他进程也随之退出
p.start()
# for j in self.jobs: # 一起回收
# j.join()

list_ = [
[1, 2, 3], [4, 5, 6], [7, 8, 9],
[2, 3, 4], [5, 6, 7], [8, 9, 10],
[3, 4, 5], [6, 7, 8], [9, 10, 11],
[5, 7, 8], [11, 13, 14], [15, 16, 17],
[10, 15, 16], [17, 18, 19], [20, 21, 22],
]
int_ = 21
# 处理僵尸进程
signal(SIGCHLD, SIG_IGN)
before = time()
Solution(list_, int_).my_process()
value = q.get()
if value:
after = time()
print(after - before)
sys.exit("array在target中")

编辑于 2020-05-24 21:40:41 回复(2)

Python

ZhiyuanChen

return target in [i for l in array for i in l]

Don’t optimize something that’s not performance critical

编辑于 2020-05-12 20:27:25 回复(0)

提交观点

问题信息

数组

来自：2015年度信息化技能...

难度：

219条回答 8618收藏 1524667浏览

通过挑战的用户

牛客69191...

2023-03-14 12:02:59
牛客50914...

2023-03-14 10:58:50
已注销

2023-03-14 10:07:41
月澈

2023-03-09 07:33:30
洞洞鞋小公主

2023-03-07 20:09:54

二维数组中的查找

输入

输出

说明

输入

输出

输入

输出

说明

最高效最简洁的写法15行给你

分析题目：

本题规则特点：

思路：

Python Solution

问题信息

热门推荐

通过挑战的用户

相关试题