前端算法题：二维数组中（每个一维数组的长度相同），左右和上下分别递增，求是否含有指定整数

CocoaChina 发布于2019-08-23 14:49 / 1950人阅读

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

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

我们先假设一个二维数组列出来，形成一个矩阵，便于我们的理解

[10, 20, 40, 60], 
[20, 30, 70, 90], 
[40, 50, 80, 110],

根据题意我们可以得到如下理论：

①最小数（min）是第一行第一个，最大数（max）是最后一行的最后一个
②每一行最大的一个数是每一行的最后一个，每一行最小一个数是每一行的第一个

根据第一个结论我们就可以先判断这个数是否在这个矩阵内

let min = array[0][0]
let max = array[array.length-1][array[0].length-1]
if (target < min || target > max) 
    return false

接下来，我们就根据第二个条件来查找：思路如下

先从第一行的最后一个数（称为J），开始比较，如果目标大于J，则与下一行的最后一个数比较，如此循环，直到目标比J小

当目标比J小时，我们就能确定是哪一行，之后你懂得，代码如下

function Find(target, array) {
            
    let i = 0
    let j = array[i].length - 1
    let min = array[0][0]
    let max = array[array.length-1][array[0].length-1]
 
    if (target < min || target > max) 
        return false
                    
    while (i < array.length && j >= 0) {
        if (array[i][j] < target) {
            i++
        } else if (array[i][j] > target) {
            j--
        } else {
            return true
        }
    }
    return false
}

云服务器 GPU云服务器 java中二维数组的长度一维数组和二维数组 python一维数组和二维数组 java中二维数组长度

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/101191.html

【刷算法】二维数组中的查找

摘要：题目描述在一个二维数组中每个一维数组的长度相同，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。分析例如二维数组，，如果按照常规的查找，从开始，那么，和都大于，接下来该怎么办呢这就陷入了一个无法进行下去的局面。题目描述在一个二维数组中（每个一维数组的长度相同），每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的...

Worktile 2019-08-23 10:22 评论0 收藏0
Union-Find并查集算法学习笔记

摘要：算法链接学习工具，，环境搭建在小伙伴的推荐下，这个学期开始上普林斯顿的算法课。一系列的整数对代表与相互连接，比如等，每一个整数代表了一个。我觉得这个可能也是并查集相关应用。这学期继续学习深入理解了就能明白了。《算法》链接：1.5 Case Study: Union-Find学习工具：mac，java8，eclipse,coursera 环境搭建在小伙伴的推荐下，这个学期开始上普林斯顿...

hzc 2019-08-14 17:08 评论0 收藏0
【剑指offer】1.二维数组查找

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

wawor4827 2019-08-23 14:32 评论0 收藏0
剑指offer中的算法题(PHP版)

摘要：二维数组中的查找在一个二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。解法有两种，一种是递归法，一种是迭代法但是递归法计算的时间复杂度是以的指数的方式递增的，如果面试中千万不要用递归法，一定要用迭代法。二维数组中的查找在一个二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和...

big_cat 2019-06-27 15:43 评论0 收藏0
【数据科学系统学习】Python # 数据分析基本操作[一] numpy

摘要：提供了使我们能够快速便捷地处理结构化数据的大量数据结构和函数。结构化数据，例如多维数据矩阵表格行数据，其中各列可能是不同的类型字符串数值日期等。基础数组和矢量计算高性能科学计算和数据分析的基础包。本篇内容为整理《利用Python进行数据分析》，博主使用代码为 Python3，部分内容和书本有出入。利用 Python 进行科学计算的实用指南。本书重点介绍了用于高效解决各种数据分析问...

wushuiyong 2019-07-31 11:11 评论0 收藏0