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

119个回答

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

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

一、给出的是方阵

[[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)
# -*- coding:utf-8 -*-
class Solution:
    # array 二维列表
    def Find(self, target, array):
        # write code here
        cols = []
        maxarray = max(array)
        minarray = min(array)
        for i in range(len(array[0][:])):
            if target <= maxarray[i] and target >= minarray[i]:
                cols.append(i)
        #print(cols)
        lownum_r =  0
        highnum_r = len(array) -1
        midnum_r = int((lownum_r + highnum_r) / 2 )
        if cols == []:
            print("false")
        else:
            for i in range(len(cols)):
                lownum_r =  0
                highnum_r = len(array) -1
                midnum_r = int((lownum_r + highnum_r) / 2 )
                while(array[midnum_r][cols[i]] != target):
                    if target < array[midnum_r][cols[i]]:
                        highnum_r =  midnum_r - 1
                    else:
                        lownum_r = midnum_r + 1
                    
                    midnum_r = int((lownum_r + highnum_r) / 2 )
                    if highnum_r < lownum_r:
                        break
                if array[midnum_r][cols[i]] == target:
                    return True
                    break
            if array[midnum_r][cols[i]] != target:
                return False
            

发表于 2019-03-06 22:53:31 回复(0)
class Solution:
    def Find(self,target,array):
        list1 = []
        print('该二维数组为:',array)
        for i in range(len(array)):
            for j in range(len(array[i])):
                list1.append(array[i][j])
        if target in list1:
            print('您输入的数字与目标值相同!')
        else:
            print('您输入的数字与目标值不同!')
while True:
    a = list(input('请输入数字:'))
    if len(a)%2== 0:
        test = 0
        break
    else:
        continue
for i_ in range(len(a)):  # 将列表元素化为整数
    a[i_] = int(a[i_])
a.sort()  # 排序
a1 = int(len(a)/2)
a2 = int(len(a))
A = a[0:a1] #将列表元素分段
B = a[a1:a2]
array = [A,B]
target = int(input('请输入目标值:'))
S = Solution()
S.Find(target,array)
发表于 2019-03-06 00:16:32 回复(0)
return target in chain(*array)
是in有优化吗?
发表于 2019-03-05 20:39:25 回复(0)
# -*- coding:utf-8 -*-
class Solution:
    # array 二维列表
    def Find(self, target, array):
        # write code here
        if not array:
            return
        row=len(array)
        col=len(array[0])
        for i in range(row):
            for j in range(col):
                if array[i][j]==target:
                    return True
        return False
发表于 2019-03-03 10:27:52 回复(0)
# -*- coding:utf-8 -*-
class Solution:
    # array 二维列表
    def Find(self, target, array):
        # write code here
        rows = len(array)
        if rows<=0:
            return False
        columns = len(array[0])
        find=False
        i=0
        j=columns-1
        while(i=0):
            current = array[i][j]
            if current==target:
                find=True
                break
            elif target>current:
                i+=1
            else:
                j-=1
        return find
发表于 2019-03-01 17:15:53 回复(0)
这是我用python过题的运行时间和内存占用, 仅供参考.

简单一点的话就遍历二分查找, 遍历二分查找的话时间复杂度是O(n * log(n)), 效果稍微差点, 但是可以继续优化, 因为二位数组是行有序且列有序的, 所以可以使用二维的二分查找, 时间复杂度就是O(log(n) * log(n)), 如果套用该思路, 用到多维数组的话(假设维度为x), 那么时间复杂度就是O((log(n)) ^ x). 我的Python代码如下:
class Solution:
    def Find(self, target, array):
        row = len(array)
        col = len(array[0])
        return self.FindHelp(target, array, 0, row - 1, 0, col - 1)

    def FindHelp(self, target, array, rb, re, cb, ce):
        row = int((rb + re) / 2)
        col = int((cb + ce) / 2)
        # 必须保证所有index的有效性且顺序是满足要求
        if 0 <= rb <= row <= re and 0 <= cb <= col <= ce:
            if array[row][col] == target:
                return True
            elif array[row][col] < target:
                return self.FindHelp(target, array, row + 1, re, cb, ce) or self.FindHelp(target, array, rb, re, col + 1, ce)
            else:
                return self.FindHelp(target, array, rb, row - 1, cb, ce) or self.FindHelp(target, array, rb, re, cb, col - 1)
        else:
            return False

编辑于 2019-03-01 16:37:11 回复(0)
# -*- coding:utf-8 -*-
class Solution:
    # array 二维列表
    def Find(self, target, array):
        # write code here
# 思路:从待查找矩阵右上角开始找,记为m,若小于m,排除此列,若大于m,排除此行
# 每次到新的右上角判断m是否为指定数字,直到超出范围后截止
        if not len(array):
            return False
        # x,y为当前角标,初始角标为右上角
        x = 0
        y = len(array[0]) - 1
        # 最大行数
        row = len(array)

        while True:
            # 如果超出了数组范围则查找失败
            if (x > row-1) | (y<0):
                return False
            m = array[x][y]
            if m == target:
                return True
            elif target > m:
                # 排除行
                    x = x + 1
            else:
                # 排除列
                    y = y - 1


发表于 2019-03-01 11:48:03 回复(0)
以左下为基点,先↑后→。
以右上为基点,先↓后←。
发表于 2019-02-24 16:26:38 回复(0)
class Solution:
    # array 二维列表
    def Find(self, target, array):
        # write code here
        #col,li=np.shape(array)
        if  not array:
            return 
        col =len(array)
        li=len(array[0])
        for i in range(0,col):
            for j in range(0,li):
                if array[i][j]==target:
                    return True
        return False
发表于 2019-02-24 15:54:55 回复(0)
class Solution:
    # array 二维列表
    def Find(self, target, array):
        # write code here
        row = len(array)
        line = len(array[0])
        if line == 0:#array is none
            return False
        for i in range(0,row):
            if target<array[i][0]:#The smallest
                return False
            elif target>array[i][line-1]:#The largest
                i+=1
            else:
                for j in range(0,line):
                    if array[i][j] == target:
                        return True
                    else:
                        j+=1

发表于 2019-02-22 14:17:39 回复(0)
先对输入的数组做检测,确保数组符合题目要求(后面来看是多此一举),然后用双层循环遍历整个数组,从右下角开始,以列为单位搜索目标数字。
结合大牛答案,发现自己没有充分利用数组特性(递增),后续改进。
编辑于 2019-02-21 16:11:55 回复(0)
First, write down an instance of the direcripted data.
Then, find the rules in the data, and set the ending condition.
# -*- coding:utf-8 -*-
class Solution:
    # array 二维列表
    def Find(self, target, array):
        deepth, length = len(array), len(array[0])
        idx_deep = deepth-1
        idx_lens = 0
        while True:
            if idx_deep < 0 or idx_lens >= length:
                return False
            if array[idx_deep][idx_lens] == target:
                return True
            elif array[idx_deep][idx_lens] > target:
                idx_deep -= 1
            elif array[idx_deep][idx_lens] < target:
                idx_lens += 1
发表于 2019-02-12 00:05:00 回复(0)
矩阵反对角线为中线(类比于一维数组查找的中点),因此可以从左下角或右上角的点出发进行查找,每次判断可以过滤掉一行或一列。
# -*- coding:utf-8 -*-
class Solution:
    # array 二维列表
    def Find(self, target, array):
        # write code here
        row = len(array)
        if row == 0:
            return False
        col = len(array[0])
        if col == 0:
            return False
        # 从左下角的点开始查找
        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-01-30 00:24:53 回复(0)

扫一扫,把题目装进口袋

牛客网,程序员必备求职神器

扫描二维码,进入QQ群

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

  • 公司地址:北京市朝阳区大屯路东金泉时代3-2708北京牛客科技有限公司
  • 联系方式:010-60728802(电话) admin@nowcoder.com
  • 牛客科技©2018 All rights reserved
  • 京ICP备14055008号-4
  • 京公网安备 11010502036488号