剑指Offer_4_二维数组中的查找-阿里云开发者社区

剑指Offer_4_二维数组中的查找

2017-12-04 932

简介： 题目描述在一个二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。例 : 1 2 8 9 　　　　 2 4 9 12 　　　　 4 7 10 13 　　　　 6 8 11 15 　　　　在这个数组中查找数字 9 , 则返回true 。

+关注继续查看

题目描述

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

例 : 1 2 8 9

　　　　 2 4 9 12

　　　　 4 7 10 13

　　　　 6 8 11 15

　　　　在这个数组中查找数字 9 , 则返回true 。查找数子5 ，则返回false 。

　分析：因为二位数组每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。

　　　　通常的思路可能是比较对角线，但是如果要查找的数相对于当前位置可能在两个区域出现，而且有重叠，

　　　　那就麻烦了。

　　　　所以一个更简单的方法是选取数组右上角的数字(当前数)，要查找的数(目标数)，如果当前数大于目标数，因为列是按从上到下递增，那么当前数所在的一列就可以排除掉了，令当前数行标减一，成为新的当前数，再去做比较。

　　　　例：

查找数字7

从右上角开始，当前数是9 ， 9大于7 ，那么9所在的列不可能有数7 ，此列排除。

行标减一后生成新的二位数组，选定新的当前数8 ， 8大于7 ，同理删去此列。

　　　　　　　　　　当前数2 ，小于7 ，此时列表加一，去除第一行。

　　　　　　当前数4 ，小于7 ，此时列表加一，去除第一行。

　　　　　　当前数7 ，等于7 ，返回true。

　　　下面分别列出c++和Java实现

c++ :

 1 #include<bits/stdc++.h>
 2 
 3 using namespace std ;
 4 
 5 int main()
 6 {
 7     int a[4][4] = {
 8                  {1,2,8,9},
 9                  {2,4,9,12},
10                  {4,7,10,13},
11                  {6,8,11,15},
12                 } ;
13     int n ;
14     cin >> n ;  // 要查找的元素
15     int i=0 ;
16     int j=3 ;
17     while((i<=3)&&(j>=0)){
18         if(a[i][j]>n){
19             j-- ;
20         }else if(a[i][j]<n){
21             i++ ;
22         }else if(a[i][j]==n){
23             cout << "yes" <<endl ;
24             break ;
25         }
26     }
27     return 0 ;
28 }

Java:

 1 import java.util.Scanner;
 2 
 3 public class Find {
 4     public static void main(String[] args) {
 5         int a[][] = {
 6                 {1, 2, 8, 9},
 7                 {2, 4, 9, 12},
 8                 {4, 7, 10, 13},
 9                 {6, 8, 11, 15},
10                      };
11         int n ;
12         Scanner cin = new Scanner(System.in) ;
13         n = cin.nextInt() ;
14         int i=0 ;
15         int j=a.length - 1;
16         while((i<=3)&&(j>=0)){
17             if(a[i][j]>n){
18                 j-- ;
19             }else if(a[i][j]<n){
20                 i++ ;
21             }else if(a[i][j]==n){
22                 System.out.println("yes");
23                 break ;
24             }
25         }
26     }
27 }