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

94个回答

添加回答
推荐
/* 思路
* 矩阵是有序的
   查看全部
编辑于 2015-06-18 16:50:07 回复(154)

该题是二分查找非递归实现在二位数组的应用。二分查找需要是一个有序的一维数组,那么题目中的二维数组是从左往右增,从上往下增,故而可以选择左下或者右上数字为参考点。
以右上为例:

1、边界条件:target<array[0][0] 或者 target > array[len(array)-1][len(array[0])] 或者 array为空 或者 array 不存在(array is None),都直接返回false, break
2、row = 0, 
   line = len(array[0])-1,
   flag = False
判断target 与 array[row][line](B)的大小:
    2.1 如果target==array[row][line],返回True, break
    2.2 如果target<array[row][line],说明目标函数值小,左移,line = line - 1, array[:][:] = array[:][:line], 继续
    2.3 如果target>array[row][line],说明目标函数值大,下移,row = row + 1, array[:][:] = array[row:][:], 继续
# -*- coding:utf-8 -*-
class Solution:
    # array 二维列表
    def Find(self, target, array):
        # write code here
        lines = len(array[0])
        rows = len(array)
        row, line = 0, lines - 1
        flag = False
        while row = 0:
            if array is None or rows == 0 or lines == 0:
                flag = False
                break
            if target  array[rows-1][lines - 1]:
                flag = False
                break

            if target == array[row][line]:
                flag = True
                break
            elif target < array[row][line]:
                line = line - 1
                array[:][:] = array[:][:lines]
            else:
              w = row + 1
                array[:][:] = array[row:][:]
        return flag
发表于 2018-10-28 23:01:11 回复(0)
a. 先测试矩阵右上角的元素值,如果该值==target, return True
b. 若该值>target, 说明这一列值都>target, 将该列去除,在缩小规模的矩阵里继续查找
c. 若该值<target, 阐明这一行值都<target, 将该行去除,在缩小规模的矩阵里继续查询
d. 首先判断矩阵缩小到无的情况,行索引>=总行数 或 列索引< 0
发表于 2018-10-22 23:35:18 回复(0)
若array 是一个二维矩阵
if i in array直接判断得不到正确结果,
if [i,j,k] in array:则可以正确判别
若array是一个一维矩阵,则可以直接使用if i in array判断。 

发表于 2018-10-20 21:06:23 回复(0)
# Pyhton
class Solution:
    # array 二维列表
    def Find(self, target, array):
        # write code here
        m = 0
        n = len(array[0]) - 1
        while m < len(array) and n >=0:
            if array[m][n] > target:
                n -= 1
            elif array[m][n] < target:
                m += 1
            elif array[m][n] == target:
                return True
        return False
// Java
public class Solution {
    public boolean Find(int target, int [][] array) {
        int i = 0;
        int j = array.length - 1;

        while (i < array[0].length && j >=0)
        {
            if (target > array[i][j])
                i++;
            else if (target < array[i][j])
                j--;
            else if (target == array[i][j])
                return true;
        }
        return false;
    }
}

发表于 2018-10-13 14:37:44 回复(0)
# -*- coding:utf-8 -*-
class Solution:
    # array 二维列表
    def Find(self, target, array):
        # write code here
        if len(array) < 1:
            return False
        rows, cols = len(array), len(array[0])
        r, c = 0, cols - 1
        while r < rows and c >= 0:
            if array[r][c] > target:
                c -= 1
            elif array[r][c] < target:
                r += 1
            else:
                return True
        return False
"""
思路: 
从右上角开始比较,小于target,则col--; 
大于target, 则row++; 
等于,则返回True;
"""
编辑于 2018-10-07 15:15:25 回复(0)
# -*- coding:utf-8 -*-
class Solution:
    # array 二维列表
    def Find(self, target, array):
        row = len(array)
        col = len(array[0])
        rfind = 0
        if col == 0:
            return False
        while rfind < row:
            if target <= array[rfind][col-1]:
                for i in range(col):
                    if target == array[rfind][i]:
                        return True
            rfind += 1
        return False


发表于 2018-09-25 14:56:50 回复(0)
# -*- coding:utf-8 -*-
class Solution:
    # array 二维列表
    def Find(self, t, a):
        n = len(a)
        m = len(a[0])
        row = n-1;col = 0
        while 1:
            if row==-1 or col==m:
                return False
            elif a[row][col]==t:
                return True
            elif t<a[row][col]:
                row = row-1
            elif t>a[row][col]:
                col = col+1
        
        # write code here

从左下角开始寻找
发表于 2018-09-22 21:07:34 回复(0)
class Solution:
    # array 二维列表
    def Find(self, target, array):
        # write code here
        if len(array)==0 or len(array[0])==0:
            return False
        elif target>array[len(array)-1][len(array[0])-1]:
            return False
        else:
            for i in range(len(array)):
                if target>array[i][len(array[0])-1]:
                    continue
                else:
                    for j in range(len(array[0])):
                        if target==array[i][j]:
                            return True
            return False
#这代码的特点是在target大于矩阵最大数时判断更快,如果target小于矩阵最大数,就循环行,比较target与每行最后数字的大小,小于才进入子循环。(思路如上,其中一个测试用例把我恶心到了,这种列表[[]]害得我得加一个判断)。
发表于 2018-09-22 11:55:28 回复(0)
【解题思路】

S1- 从数组的右上角开始,若target大于右上角的值则表示不在该行,行数i++;

S2- 若target 小于右上角的值则表示不在该列,列数j--;

S3- 若target等于右上角的值则返回;

S4- 若i>数组的行数或者列大于数组的列数则未找到停止。

# -*- coding:utf-8 -*-
class Solution:
    # array 二维列表

    def Find(self, target, array):
        # write code here
        cols = len(array[0])-1
        rows = len(array)-1
        i=0;j=cols
        while i<=rows and j>=0:
            if target == array[i][j]:
                return True
            elif target > array[i][j]:
                i+=1
            elif target < array[i][j]:
                j-=1
        return False

发表于 2018-09-17 10:53:42 回复(0)
'''
解题思路:
*每一行或者每一列都是有序数组,可以用二分法查找;
*另外,输入矩阵并没有说明数组的h==w,所以:
先判断h和w哪个更短,选择更短的一维进行遍历,每次遍历采用二分法查找一维子数组。
'''
# -*- coding:utf-8 -*-
class Solution:
    # array 二维列表
    def Find(self, target, array):
        # write code here
        def binary_search(target,vector):
            begin, end = 0, len(vector)-1
            while begin<=end:
                middle = (begin+end)//2
                if target == vector[middle]:
                    return middle
                elif target < vector[middle]:
                    end = middle-1
                else:
                    begin = middle+1
            return -1
        h = len(array)
        w = len(array[0])
        if h<=w:
            for i in range(h):
                result = binary_search(target, array[i])
                if result != -1:
                    return True
            return False
        else:
            for i in range(w):
                result = binary_search(target, array[:][i])
                if result != -1:
                    return True
            return False

发表于 2018-09-12 23:16:34 回复(0)
# -*- coding:utf-8 -*-
class Solution:
    # array 二维列表
    def Find(self, target, array):
        # write code here
        row = 0
        col =len(array[0])-1
        if array == None:
            return Flase
        while row < len(array) and col >= 0:
            if array[row][col] == target:
                return True
            elif array[row][col] < target:
                row += 1
            else:
                col -=1
        return False
 
python 在二维数组中的array的格式是array[row][column],所以在遍历时需要统计多维数组的行数和列数的时候,如果是直接对数组名求len(array),那得到的是多维数组的行数,如果是对某一行求len(array[i])则是求第i维的长度,也即是列数。对这个概念了解清楚,就可以慢慢写出来、
发表于 2018-09-10 23:15:23 回复(0)
array转成set,检查元素是否在集合中。

# -*- coding:utf-8 -*-
class Solution:
    # array 二维列表
    def Find(self, target, array):
        # write code here
        s = set()
        for i in array:
            s = s|set(i)
        if target in s:
            return 1
        return 0

发表于 2018-09-08 22:05:52 回复(0)
# -*- coding:utf-8 -*-
# Python解法,直接判断目标整数是否在二维数组里的一位数组里面
class Solution:
    # array 二维列表
    def Find(self, target, array):
        # write code here
        for L in array:
            if target in L:
                return True
            else:
                pass
        return False


发表于 2018-09-07 13:08:57 回复(0)
开始没审清楚题,以为要先按要求排序,在找数,如果直接输入二维数组,问题就集中在1.二维数组的输入(利用eval函数可将任意列表的字符串类型还原回列表)2.找数。思想:依次将目标数与从左下角元素开始的数相比较,大于左下角元素则向右找,小于则向上找。此处关键之处在于左下角元素的定位
class Solution(object):  def Find(self, target, array): # write code here  rows = len(array) - 1 #二维数组行数len(数组名),此处为索引,所以要减1 
      cols = len(array[0]) - 1 #二维数组列数len(数组名[0])    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 1    return 0   obj=Solution()
array=list(eval(input("输入二维数组:")))
number=int(input("输入一个整数:"))
flag=obj.Find(number,array) if flag==1:
    print("数组存在此数") else:
    print("数组没有此数")

发表于 2018-08-29 11:27:09 回复(0)
# -*- coding:utf-8 -*-
class Solution:
    def Find(self,target,array):
        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
                        
                   




发表于 2018-08-28 16:29:34 回复(0)
# -*- coding:utf-8 -*-
class Solution:
    # array 二维列表
    def Find(self, target, array):
        # write code here
        for each in array:
            if target in each:
                return True
        return False

编辑于 2018-08-27 23:24:27 回复(0)
python 版

    def Find(self, target, array):
        # write code here
        row = len(array)
        col  = len (array[0])
        i = 0
        j = col-1
        while (i<=row-1 and j >=0):
            #print(arr[i][j]) 不放心 可以打印出来看看是不是按轨迹走的
            if array[i][j]==target:
                return True
            elif array[i][j]>target:
                j = j-1
            else:
                i = i+1
        return False

发表于 2018-08-26 12:14:21 回复(0)
数组为右下增大,最后一列的数字都是每一行中的最大值, 从中查找所在的行号.
[[1,2,3], [5,6,7], [7,8,9]] 最后一列[3,7,9], 查找数字为8, 8>3,8>7, 8<9 则在第三行
然后再行内折半查找对应的数字,如果找不到就报错.
发表于 2018-08-12 20:58:43 回复(0)

从左下角开始遍历,当前值小于target则向右移,大于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 i >= 0 and j <= col:
        if target < array[i][j]:
            i -= 1
        elif target > array[i][j]:
            j += 1
        else:
            return True
    return False
发表于 2018-08-05 12:31:52 回复(0)

扫一扫,把题目装进口袋

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

扫描二维码,进入QQ群

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

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