题目描述

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

解题思路

从题意我们可以知道最小数是第一行第一个，最大数是最后一行的最后一个，每一行最大的一个数是每一行的最后一个，每一行最小一个数是每一行的第一个。
所以我们从第一行的最后一个数开始比较假定这个值为 temp，如果目标值 target 大于 temp，那么与下一行的数值进行比较，因为下一行的值比上一行的值大；如果目标值 target 小于 temp，那么与前一列的数值进行比较，因为前一列的值比后一列的值小。如此循环直到找到这个数返回 true，或者所有的数都被查找过返回 false。

代码实现

  1. import java.util.Scanner;
  3. public class Problem1 {
  4.     public static boolean Find(int target, int [][] array) {
  5.         if(array == null){
  6.             return false;
  7.         }
  8.         int n = array.length;
  9.         int m = array[0].length;
  10.         int i = 0;
  11.         int j = m - 1;
  12.         while(i < n && j >= 0){
  13.             int temp = array[i][j];
  14.             if(target < temp){
  15.                 j--;
  16.             }
  17.             else if(target > temp){
  18.                 i++;
  19.             }
  20.             else{
  21.                 return true;
  22.             }
  23.         }
  24.         return false;
  25.     }
  26.     public static void main(String[] args) {
  27.         Scanner cin = new Scanner(System.in);
  28.         int[][] array = new int[2][2];
  29.         for (int i = 0; i < 2; i ++) {
  30.             for (int j = 0; j < 2; j ++) {
  31.                 array[i][j] = cin.nextInt();
  32.             }
  33.         }
  34.         int target = cin.nextInt();
  35.         System.out.println(Find(target, array));
  36.     }
  37. }