用递归查找有序二维数组的方法详解

假设给定一个有序二维数组，每一行都是从左到右递增，每一列都是从上到下递增，如何完成一个函数，输入这样一个二维数组和一个整数，判断这个整数是否在这个二维数组中。
假设一个4×4的有序二维数组：
          1          2          8          9
          2          4          9          12
          4          7          10        13
          6          8          11        15
要查找的数字为6。
算法的核心思想是，先取最左上角的数字9,因为9比6大，所以可以排除比9大的数字，也就是第四列，然后取8，同理排除第三列，再取2，比6小，可排除比2小的数字，也就是第一行，同理取4，排除第二行，取7，排除第二列，取4，排除第三行，取6，相等，返回true。
这里我们用递归实现，代码为：


代码如下:

public class FindMatrixNumber {
 private static FindMatrixNumber instance;
 private static boolean found = false;
 public static FindMatrixNumber getInstance() {
  if (instance == null) {
   instance = new FindMatrixNumber();
  }
  return instance;
 }
 public static boolean find(int matrix[][], int number) {
  if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
   return false;
  } else {
   System.out.println("****Start finding****");
   findMatrixNumber(matrix, matrix.length, 0, matrix[0].length,
     number);
   System.out.println("*****End finding*****");
  }
  return found;
 }
 private static void findMatrixNumber(int matrix[][], int rows, int row,
   int columns, int number) {
  if (row > rows - 1)
   return;
  int cornerNumber = matrix[row][columns - 1];
  System.out.println(cornerNumber);
  if (cornerNumber == number) {
   found = true;
   return;
  } else if (cornerNumber < number) {
   findMatrixNumber(matrix, rows, ++row, columns, number);
  } else if (cornerNumber > number) {
   findMatrixNumber(matrix, rows, row, --columns, number);
  }
 }
}

测试代码为：


代码如下:

public class TestFindMatrixNumber {

public static void main(String[] args) {
  int matrix[][] = {{1,2,8,9},{2,4,9,12},{4,7,10,13},{6,8,11,15}};
  System.out.println(FindMatrixNumber.find(matrix, 6));
 }

}

测试代码运行结果为：


代码如下:

****Start finding****
9
8
2
4
7
4
6
*****End finding*****
true

赞 (0)

相关推荐

  • 归并算法之有序数组合并算法实现

    归并算法之有序数组合并算法实现 一个简单的有序数组合并算法:写一个函数,传入 2 个有序的整数数组,返回一个有序的整数数组.实现相当简单,创建一个长度为这两个长度之和的数组,然后分别用三个指针指向这三个数组,找到这两个数组中各个元素在合并数组中的位置并插入,直到某个数组指针到达尾部.再将另一个数组剩下的所有元素,直接放入归并数组尾部.算法的简单实现,需要注意的是对参数的校验,判断数组是否有序. public class MergeOrderedArray { public static int[

  • C语言实现在数组A上有序合并数组B的方法

    本文实例讲述了C语言实现在数组A上有序合并数组B的方法,分享给大家供大家参考.具体分析如下: 题目:数组A和数组B均有序,数组A有足够大内存来容纳数组B,将数组B有序合并到数组A中 分析:如果由前至后合并,复杂度将会是O(N2),这样的复杂度显然不是最优解,利用两个指针指向两个数组的尾部,从后往前遍历,这样的复杂度为O(n2) 由此可以写出下面的代码: #include <iostream> #include <algorithm> #include <iterator>

  • Python实现二维有序数组查找的方法

    本文实例讲述了Python实现二维有序数组查找的方法.分享给大家供大家参考,具体如下: 题目:在一个二维数组中,每一行都按照从左到右递增的顺序排序,每一列都按照从上到下递增的顺序排序.请完成一个函数,输入这样的一个二维数组和一个整数,判断数组中是否含有该整数. 这题目属于比较简单但又很不容易想到的,问了两个同学,大家一时都没有想出来怎么解决比较快.第一反应都是二分查找.对于每一行进行二分查找,然后查找过程可以把某些列排除掉,这是大家都能想到的基本的思路. 比较好的另一种思路是,首先选取数组右上角

  • javascript 折半查找字符在数组中的位置(有序列表)

    复制代码 代码如下: /** * 折半查找字符在数组中的位置(有序列表) * @param array 被检索的数组 * @param x 要查找的字符 * @type int * @returns 字符在数组中的位置,没找到返回-1 */ function binarySearch(array,x){ var lowPoint=1; var higPoint=array.length; var returnValue=-1; var midPoint; var found=false; whi

  • php实现有序数组打印或排序的方法【附Python、C及Go语言实现代码】

    本文实例讲述了php实现有序数组打印或排序的方法.分享给大家供大家参考,具体如下: 有序的数组打印或排序对于php来讲非常的简单了这里整理了几个不同语言的做法的实现代码,具体的我们一起来看这篇php中有序的数组打印或排序的例子吧. 最近有个面试题挺火的--把2个有序的数组打印或排序,刚看到这个题的时候也有点蒙,最优的算法肯定要用到有序的特性. 思考了一会发现也不是很难,假如数组是正序排列的,可以同时遍历2个数组,将小的值进行排序,最后会遍历完一个数组,留下一个非空数组,而且剩下的值肯定大于等于已

  • php判断一个数组是否为有序的方法

    本文实例讲述了php判断一个数组是否为有序的方法.分享给大家供大家参考.具体分析如下: 这段代码的时间复杂度为O(n) <?php function JudegSortArray($array) { if ($array [0] > $array [1]) { $flag = 1; } else { $flag = 0; } $temp = $flag; $len = count ( $array ); for($i = 1; $i < $len; $i ++) { if ($flag

  • java实现向有序数组中插入一个元素实例

    整理文档,搜刮出一个java实现向有序数组中插入一个元素,稍微整理精简一下做下分享 package cn.jbit.array; import java.util.*; public class Insert { public static void main(String[] args) { //字符排序 char[] chars = new char[9]; chars[0] = 'a'; chars[1] = 'c'; chars[2] = 'u'; chars[3] = 'b'; cha

  • 合并有序数组的实现（java与C语言）

    合并有序数组的实现 java版本: 实例代码 public class Merge { //合并有序数组 public static void mergeSort(int a[], int b[], int c[]) { int n = a.length, m = b.length; int i, j, k; i = j = k = 0; while (i < n && j < m) { if (a[i] < b[j]) { c[k++] = a[i++]; } else

  • js有序数组的连接问题

    1.前言 昨天碰到一道关于如何解决有序数组的连接问题,这是一个很常见的问题.但是这里要考虑到代码的效率问题,因为要连接的数组都是有序的,这是一个非常重要的前提条件. 2.简单但效率不高的算法 我首先想到的是使用内置的concat方法,然后再对其进行排序,这种方法完全没有考虑到数组是有序的前提条件,代码如下: 复制代码 代码如下: function concatSort(arrA,arrB){      return arrA.concat(arrB).sort(); } 为了弄清楚sort排序到

  • 用递归查找有序二维数组的方法详解

    假设给定一个有序二维数组,每一行都是从左到右递增,每一列都是从上到下递增,如何完成一个函数,输入这样一个二维数组和一个整数,判断这个整数是否在这个二维数组中.假设一个4×4的有序二维数组:          1          2          8          9          2          4          9          12          4          7          10        13          6          8 

  • js处理自己不能定义二维数组的方法详解

    复制代码 代码如下: var a= new Array(new Array(1,2),new Array('b','c')); document.write(a[1][1]); 说白了,就是利用for循环定义二维数组! ?<script language="javascript" type="text/javascript">     function Array_2(nRow,nColumn){         var array1=new Array

  • java二维数组基础知识详解

    目录 1. 查找 2. 顺序查找 3. 二分查找 4. 多维数组 4.1 二维数组 175 4.2 二维数组细节 5. 二维数组的使用方式 176 6. 二维数组的动态初始化 1.先声明:类型 数组名[][]; 再定义(开辟空间) 数组名 = new 类型[大小][大小] 2.动态初始化-列数不确定 178 7. 二维数组的静态初始化 179 8. 二维数组练习 180 8.1 int arr[][]={{4,6},{1,4,5,7},{-2}}; 遍历该二维数组,并得到和 1. 查找 1) 顺

  • Python实现在图像中隐藏二维码的方法详解

    Python实现在图像中隐藏二维码的方法详解

    目录 一.前言 二.隐写 三.位平面分解 3.1 图像 3.2 位平面 3.3 位平面分解 3.4 位平面合成 四.图像隐写 一.前言 在某个App中有一个加密水印的功能,当帖子的主人开启了之后.如果有人截图,那么这张截图中就是添加截图用户.帖子ID.截图时间等信息,而且我们无法用肉眼看出这些水印. 这可以通过今天要介绍的隐写技术来实现,我们会通过这种技术,借助Python语言和OpenCV模块来实现在图像中隐藏二维码的操作.而且这个二维码无法通过肉眼看出. 二.隐写 隐写是一种类似于加密却又不

  • php中二维数组排序问题方法详解

    PHP中二维数组排序,可以使用PHP内置函数uasort() 示例一: 使用用户自定义的比较函数对数组中的值进行排序并保持索引关联 回调函数如下:注意回调函数的返回值是负数或者是false的时候,表示回调函数的第一个参数在前,第二个参数在后排列 $person = array( array('num'=>'001','id'=>6,'name'=>'zhangsan','age'=>21), array('num'=>'001','id'=>7,'name'=>'

  • PHP基于phpqrcode类生成二维码的方法详解

    PHP基于phpqrcode类生成二维码的方法详解

    本文实例讲述了PHP基于phpqrcode类生成二维码的方法.分享给大家供大家参考,具体如下: 使用PHP语言生成二维码,还是挺有难度的,当然调用生成二维码图片的接口(比如:联图网http://www.liantu.com/的接口)除外,如果自己写代码生成,真的无从下手.然而,我们可以使用phpqrcode这个现成的类文件,PHP二维码生成类库,利用它可以轻松生成二维码. 前期准备: 1.phpqrcode类文件下载,下载地址:https://sourceforge.net/projects/p

  • PHP生成二维码与识别二维码的方法详解【附源码下载】

    PHP生成二维码与识别二维码的方法详解【附源码下载】

    本文实例讲述了PHP生成二维码与识别二维码的方法.分享给大家供大家参考,具体如下: 二维码的分类 线性堆叠式二维码 矩阵式二维码 二维码的优缺点 优点 信息容量大 编码范围广 容错能力强 译码可靠性高 可引入加密措施 成本低,易制作 缺点 二维码技术成为手机病毒.钓鱼网站传播的新渠道 信息泄密 目前流行的三大国际标准 PDF417:不支持中文 DM:专利未公开,需支付专利费用 QR CODE:专利公开,支持中文 QR CODE 纠错能力 L级:约可纠错7%的数据码字 M级:约可纠错15%的数据码

  • JavaScript动态创建二维数组的方法示例

    JavaScript动态创建二维数组的方法示例

    本文实例讲述了JavaScript动态创建二维数组的方法.分享给大家供大家参考,具体如下: 学过C语言的我太耿直 一般这种情况下我会直接 var arr = new Array[10][10]; 但是不出意外的话这样是会报错的,因为在js中根本没有这样的语法 在这之前,让我们先来回顾一下js中是怎么样创建一维数组的: 使用数组直接量,这个是最简单的,在方括号内将数组元素用逗号隔开即可: var arr = [ ]; //空数组 var s = [1,2,3,4]; //4个元素的数组 var n

  • java String 转成Double二维数组的方法

    WHY 朋友在群里求助一个问题,问题原型是这样的: String str = "{{10.14, 11.24, 44.55, 41.01},{12.10, 14.21, 52.14, 50.44},{14.44, 16.12, 45.42, 47.55}}"; 转成double[][]{ {10.14, 11.24, 44.55, 41.01}, {12.10, 14.21, 52.14, 50.44}, {14.44, 16.12, 45.42, 47.55} } 也就是把一个可以转

  • PHP实现一维数组转二维数组的方法

    本文实例讲述了PHP实现一维数组转二维数组的方法.分享给大家供大家参考.具体实现方法如下: <?php $asr[1] = array("a","b","c","d"); $asr[2] = array("a","b","c","d"); $asr[3] = array("a","b","c&

随机推荐