目录

 

---

1 问题描述

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

 

 

---

2 解决方案

2.1定位法

下面算法的时间复杂度为O(m + n)，空间复杂度为O(1)。

具体代码如下：

package com.liuzhen.practice;public class Main {        public boolean YoungMatrix(int[][] A, int key) {        int i = 0, j = A[0].length - 1;        int temp = A[i][j];        while(true) {            if(temp == key) {                return true;            } else if(temp < key && i < A.length - 1) {                temp = A[++i][j];            } else if(temp > key && j > 0) {                temp = A[i][--j];            } else {                return false;            }        }    }        public static void main(String[] args) {        Main test = new Main();        int[][] A = {
   {
   1,2,8,9},{
   2,4,9,12},{
   4,7,10,13},{
   6,8,11,15}};        if(test.YoungMatrix(A, 6))             System.out.println("矩阵A中包含元素6");        else            System.out.println("矩阵A中不包含元素6");        if(test.YoungMatrix(A, 5))             System.out.println("矩阵A中包含元素5");        else            System.out.println("矩阵A中不包含元素5");    }}

 

 运行结果：

矩阵A中包含元素6矩阵A中不包含元素5

 

 

 

参考资料：

   1.《编程之法面试和算法心得》  July 著