首页 > 试题广场 > 二维数组中的查找
[编程题]二维数组中的查找
在一个二维数组中(每个一维数组的长度相同),每一行都按照从左到右递增的顺序排序,每一列都按照从上到下递增的顺序排序。请完成一个函数,输入这样的一个二维数组和一个整数,判断数组中是否含有该整数。
推荐
/* 思路
* 矩阵是有序的,从左下角来看,向上数字递减,向右数字递增,
* 因此从左下角开始查找,当要查找数字比左下角数字大时。右移
* 要查找数字比左下角数字小时,上移
*/

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 回复(218)
1. 先剔除空数列对结果的影响。
2.从右上角开始遍历:#x为遍历到的值
如果x大于目标,列数减一。
如果x小于目标,行数加一。
发表于 2019-11-02 23:58:19 回复(0)
时间复杂度 O(M + N),空间复杂度 O(1)。其中 M 为行数,N 为 列数。
从二维数组右上角开始查找,若target小于当前位置的值则应向左继续查找;反之,若target大于当前位置的值则应向下查找。

# -*- coding:utf-8 -*-
class Solution:
    # array 二维列表
    def Find(self, target, array):
        # write code here
        m, n = len(array), len(array[0])
        i, j = 0, n - 1             # 从右上角开始查找
        while i < m and j >= 0:
            if target == array[i][j]:
                return True
            elif target > array[i][j]:
                i += 1
            else:
                j -= 1
        return False


发表于 2019-10-24 16:11:59 回复(0)
把二维数组合并,再遍历
发表于 2019-10-15 21:42:29 回复(0)
从左下到右上遍历,每次筛选一行
# -*- coding:utf-8 -*-
class Solution:
    # array 二维列表
    def Find(self, target, array):
        # write code here
        height=len(array)
        width=len(array[0])
        i=height-1
        j=0
        while i>=0 and j<=width-1:
            if array[i][j]==target:
                return True
            elif array[i][j]<target:
                j+=1
            else:
                i-=1
        return False


发表于 2019-10-11 20:57:49 回复(0)
# -*- coding:utf-8 -*-

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

发表于 2019-09-21 17:03:44 回复(1)
class Solution:

    def Find(self,target,array):
        if not array[0]:return False
        if target < array[0][0]:return False
        if target > array[-1][-1]: return False

        row =len(array)
        col = len(array[0])
        print(row,col)
        for i in range(row):
            print(i)
            first = 0
            last = col - 1
            while first <= last:
                mid = (last + first) // 2
                if array[i][mid] > target:
                    last = mid -1
                elif array[i][mid] < target:
                    first = mid + 1
                else:
                    return True

        return False
为了通过题目,使用了一次二分,其实可以使用两次二分。
编辑于 2019-09-19 16:53:35 回复(0)
# -*- coding:utf-8 -*-
class Solution:
    # array 二维列表
    def Find(self, target, array):
        # write code here
        if array == [[]]:
            return False
        for i in range(len(array)):
            if array[i][0]<=target and array[i][-1]>=target:
                for j in array[i]:
                    if j == target:
                        return True
        return False
发表于 2019-09-17 22:47:50 回复(0)
# -*- coding:utf-8 -*-
class Solution:
    # array 二维列表
    def Find(self, target, array):
        # write code here
        for i in range(0,len(array)):
            if target in array[i]:
                return True
        return False
用python真是不要太简单啊。。。。
发表于 2019-09-11 22:10:27 回复(1)
# -*- coding:utf-8 -*-
class Solution:
    # array 二维列表
    def Find(self, target, array):
        # write code here
        for arr_x in array:           
            if target in arr_x:
                return True
        return False
先将二维数组拆分成一维数组
再使用in判断要查找的在不在该一维数组中
如果存在 返回True
如果遍历到最后都不存在返回False
发表于 2019-09-04 19:56:05 回复(0)
class Solution:
    def Find(self,target,array):
        # 纵列
        rows = len(array) - 1
        i = rows
        # 横列
        cols = len(array[0]) - 1
        j = 0
        # 纵列大于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-09-03 19:39:55 回复(0)
暴力遍历
flag=False
for index in range(len(index)):
  if target in array[index]:
    flag=True
 return flag
 
发表于 2019-09-03 10:05:17 回复(0)

利用相邻数组之间的关系,箭头方向是由小指大。
通过整理以及其规律,可以将target的范围划定在两个阴影部分(结合代码):

def Find(target, array):
    long = len(array)     #最大行
    long1 = len(array[0]) #最大列
    if long == 1 and long1 ==0: #保证有data
        print("false")
        return 0
    x = 0
    y = 0
    xx = 0
    yy = 0
    if target < array[0][0]: # 小于最小必为false
        print("false")
        return 0
    while True:           #先以对角线进行搜索, 缩小搜索范围
        if target > array[x][y]:
            x = x + 1
            y = y + 1
            if x > long-1 and y > long1-1:    # 大于最大必为false
                print("false")
                return 0
            if x > long-1:
                x = x - 1
            if y > long1-1:
                y = x - 1
            xx = x     # xx,yy查询 在array[0:xx-1][0:yy-1](简易注释,能看明白就好)必不存在 target
            yy = y
        elif target == array[x][y]:  # 缩小范围中,也不能忘了判断 对角线上是否有target
            print("true")
            return 1
        else:
            break
    # 后期搜索包括两个对称部分 :
    # 第一部分:y>= yy
    len_ = 0
    len__ = yy
    while True:
        for n in range(xx-len_):
            if target < array[n][len__]:
                len_ = len_ + 1
                break
            if target == array[n][len__]:
                print ("true")
                return 1
        len__ = len__ + 1
        if len__==long1:
            break
        # 第一部分:y<yy

    len_ = 0
    len__ = xx
    while True:
        for n in range(yy-len_):
            if target < array[len__][n]:
                len_ = len_ + 1
                break
            if target == array[len__][n]:
                print ("true")
                return 1
        len__ = len__+1
        if len__ == (long):
            print ("false")
            return 0
本人学徒一位,望指错,相互交流



发表于 2019-08-30 01:35:33 回复(0)
用python遍历二维数组
# -*- coding:utf-8 -*-
class Solution:
    # array 二维列表
    def Find(self, target, array):
        # write code here
        num = 0
        a = target
        b = array
        for i in range(len(array)):
            for j in range(len(array[i])):
                if a == array[i][j]:
                    num += 1
        return num
发表于 2019-08-29 16:50:35 回复(0)
# -*- coding:utf-8 -*-
class Solution:
    # array 二维列表
    def Find(self, target, array):
        # write code here
        row = len(array)
        col = len(array[0])
        i = 0
        j = col - 1
        flag = False
        while i < row and j >= 0: 
            if target > array[i][j]:
                i += 1
            elif target == array[i][j]:
                flag = True
                break
            else:
                j -= 1
        return flag


发表于 2019-08-28 13:09:03 回复(0)
有序矩阵。
思路:从左下角或者右上角开始比较
发表于 2019-08-28 10:20:33 回复(0)
# -*- coding:utf-8 -*-
class Solution:
    # array 二维列表
    def Find(self, target, array):
        # write code here
        if array == None:
            return False
        # 从二维数组右上角开始遍历
        i = 0
        rows = len(array)  # 行的长度
        columns = len(array[0])  # 列的长度
        j = columns - 1
        while i < rows and j >= 0:
           # 在数组中找到data并返回
            if array[i][j] == target:
                return True
            # 当前遍历到数组中的值大于data,data肯定不在这一列中
            elif array[i][j] > target:
                j -= 1
           # 当前遍历到数组中的值小于data,data肯定不在这一行中
            else:
                i += 1
        return False

发表于 2019-08-19 21:42:35 回复(0)
# encoding:utf-8
"""
    从二维数组的右上角开始向下或者向左寻
"""
class Solution:
    def Find(self, target, array):
        i = 0
        j = len(array[0]) - 1
        while i < len(array) and j >= 0:
            if target == array[i][j]:
                return True
            elif target > array[i][j]:
                i += 1
            else:
                j -= 1
        return False
发表于 2019-08-15 15:00:03 回复(0)
class Solution:
    # array 二维列表
    def Find(self, target, array):
        if len(array) == 0 or len(array[0]) == 0:
            return False
        # write code here
        min = array[0][0]
        max = array[len(array) - 1][len(array[0]) - 1]
        if target < min or target > max:
            return False

        for i in range(len(array)):
            if array[i][0] <= target <= array[i][-1] :
                r = len(array[i]) 
                for j in range(r):
                    if (target == array[i][j]):
                        return True
        return False
暴力
发表于 2019-08-13 14:04:05 回复(0)
def find(tar,array):
    i = 0
    j = 0
    k = len(array)
    l = len(array[0])
    for i in range(k):
        for j in range(l):
            if array[i][j] == tar:
                return True        #return结束所有循环
    return False

发表于 2019-08-09 16:22:50 回复(0)
会有重复元素存在,这个比较坑了,刚开始以为没有重复元素,大家注意了。

运行时间:231ms

占用内存:5856k

Python版本:
def Find(self, target, array):
        # write code here
        m,n=len(array),len(array[0])
        if (m==0) | (n==0):
            return False
        if target<array[0][0] | target>array[m-1][n-1]:
            return False  #比最大的大,比最小的小,不存在
        for i in range(0,m):
            left=0
            right=n-1
            if (target<array[i][left]) | (target>array[i][right]):
                continue #比这行最小的小,或者比这行最大的大,到下一行去找
            if (target==array[i][left]) | (target==array[i][right]):
                return True  #找到了
            while(left<right):
                if target>array[i][left]:
                    left+=1
                if target<array[i][right]:
                    right-=1
                if target==array[i][left] or target==array[i][right]:
                    return True  #找到了
            continue
        return False

编辑于 2019-08-08 12:54:19 回复(0)