首页 > 试题广场 >

二维数组中的查找

[编程题]二维数组中的查找
  • 热度指数：2367261 时间限制：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。

数据范围：矩阵的长宽满足 ， 矩阵中的值满足
进阶：空间复杂度 ，时间复杂度
示例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头像 曰无衣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号头像 牛客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头像 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号头像 牛客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头像 在下小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头像 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头像 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头像 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头像 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头像 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头像 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号头像 牛客720457535号

注意有特例的输入

array=[[]]

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

编辑于 2020-07-21 11:09:37 回复(0)
Python
牛客279485353号头像 牛客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头像 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号头像 牛客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号头像 橘子汽水超人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号头像 牛客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头像 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条回答 1520888浏览

热门推荐

通过挑战的用户

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号