行列有序的二维数组查找_二维行列有序-程序员宅基地

技术标签：矩阵数据结构与算法

题目

在一个二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。

请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。

输入描述:

array：待查找的二维数组

target：查找的数字

输出描述:

查找到返回true，查找不到返回false

分析与解法
解法一、分治法
这种行和列分别递增的矩阵，有一个专有名词叫做杨氏矩阵，由剑桥大学数学家杨表在1900年推提出，在这个矩阵中的查找，俗称杨氏矩阵查找。
以查找数字6为例，因为矩阵的行和列都是递增的，所以整个矩阵的对角线上的数字也是递增的，故我们可以在对角线上进行二分查找，如果要找的数是6介于对角线上相邻的两个数4、10，可以排除掉左上和右下的两个矩形，而在左下和右上的两个矩形继续递归查找，如下图所示

解法二、定位法
首先直接定位到最右上角的元素，再配以二分查找，比要找的数（6）大就往左走，比要找数（6）的小就往下走，直到找到要找的数字（6）为止，这个方法的时间复杂度O（m+n）。如下图所示：

<?php 
   function search($arr, $key){
        $y = count($arr);
        $x = count($arr[0]);
        $i = 0; $j = $x-1;
        $base = $arr[$i][$j];
        while(true){
            if($key == $base){
                return 'arr['.$i.']['.$j.']';
            }else if($key < $base && $j>0){
                $base = $arr[$i][--$j]; 
            }else if($key > $base && $i<$y-1){
                $base = $arr[++$i][$j];
            }
        }
    } 

    $arr = array(
        array(1,2,8,9),
        array(2,4,9,7),
        array(4,7,10,13),
        array(6,8,11,15),
    );

    echo search($arr, 6);
?>

本文链接：https://blog.csdn.net/guugle2010/article/details/50916487

原作者删帖不实内容删帖广告或垃圾文章投诉

智能推荐

Jquery 多选下拉列表插件jquery multiselect-程序员宅基地

文章浏览阅读286次。有一个多选的需求，在网上找到了这个插件：multiselecthttps://github.com/ehynds/jquery-ui-multiselect-widgetcsdn博客上有这个插件的介绍，不少童鞋都问了这么个问题，怎么获取选中的值？真是个好问题，因为我在看demo的时候也发现了这个问题，呵呵！先简单说说这个插件： jquery-multisel..._multiselect 多级多选插件 checkbox

解决android studio打包后安装APK提示“签名不一致，该应用可能已被修改。“_签名不一致该应用可能已被修改-程序员宅基地

文章浏览阅读8.4k次，点赞5次，收藏15次。现象解决办法修改applicationId名_签名不一致该应用可能已被修改

PHP用户缓存APCU_php apcu 100%-程序员宅基地

文章浏览阅读6.1k次。故事APCu 是老牌 PHP 字节码和对象缓存缓存器 APC 的分支，具体由来还得讲个故事。首先提一下，PHP 如果公用多个缓存器是会冲突的，例如同样都是字节码缓存器，OPcache 和 eAccelerate 同时安装就会起冲突甚至报错；而 XCache 同时有字节码缓存器和对象缓存，和 OPCache 共存也是会起冲突的。在 PHP 5.5 之前是没有 OPcache 这个缓存器_php apcu 100%

Android progressbar设置虚线进度条时不显示的解决办法_android 进度条设置processdrawable后不显示进度条-程序员宅基地

文章浏览阅读1.6k次。最近公司要求实现进度条，除了渐变的要求，还要有是虚线，我想定义一个shape即可，结果发现写好的资源文件，在预览图上面是虚线，可是运行到手机上就是实现，如下代码：<ProgressBar android:id="@+id/progress_ckbg" style="?android:attr/progressBarStyleHorizon..._android 进度条设置processdrawable后不显示进度条

HDU-1753 大明A+B，小数A+B_小数a+bc语言-程序员宅基地

文章浏览阅读117次。话说，经过了漫长的一个多月，小明已经成长了许多，所以他改了一个名字叫“大明”。这时他已经不是那个只会做100以内加法的那个“小明”了，现在他甚至会任意长度的正小数的加法。现在，给你两个正的小数A和B，你的任务是代表大明计算出A+B的值。Input本题目包含多组测试数据，请处理到文件结束。每一组测试数据在一行里面包含两个长度不大于400的正小数A和B。Output请在一行里面输出输出A+B的值，请输出最简形式。详细要求请见Sample Output。Sample Input1.1 2.91_小数a+bc语言

Java中如何将List拆分为多个小list集合_java把list分成多个list-程序员宅基地

文章浏览阅读2w次，点赞11次，收藏19次。文章目录一、如何将List拆分为多个小list写在前面：我是「境里婆娑」。我还是从前那个少年，没有一丝丝改变，时间只不过是考验，种在心中信念丝毫未减，眼前这个少年，还是最初那张脸，面前再多艰险不退却。写博客的目的就是分享给大家一起学习交流，如果您对 Java感兴趣，可以关注我，我们一起学习前言：在平常写代码时候可能会遇到需要将一个大list拆分多个小list，进行一些业务处理。一、如何将List拆分为多个小list如何将List拆分多个小list，首先我们需要list.sublist这个方法_java把list分成多个list