剑指Offer_4_二维数组中的查找

题目描述

      在一个二维数组中,每一行都按照从左到右递增的顺序排序,每一列都按照从上到下递增的顺序排序。请完成一个函数,输入这样的一个二维数组和一个整数,判断数组中是否含有该整数。
     例 :     1   2    8     9
     2   4    9    12
     4   7   10   13
     6   8   11   15
    在这个数组中查找数字 9 ,  则返回true 。 查找数子5 ,则返回false 。
 
 分析 : 因为二位数组每一行都按照从左到右递增的顺序排序,每一列都按照从上到下递增的顺序排序。
      通常的思路可能是比较对角线,但是如果要查找的数相对于当前位置可能在两个区域出现,而且有重叠,
      那就麻烦了。
 
      所以一个更简单的方法是选取数组右上角的数字(当前数),要查找的数(目标数),如果当前数大于目标数,因为列是            按从上到下递增,那么当前数所在的一列就可以排除掉了,令当前数行标减一,成为新的当前数,再去做比较。
    例:
                剑指Offer_4_二维数组中的查找     查找数字7 
 
       剑指Offer_4_二维数组中的查找   从右上角开始,当前数是9 , 9大于7 ,那么9所在的列不可能有数7 , 此列排除 。
      剑指Offer_4_二维数组中的查找        行标减一后生成新的二位数组,选定新的当前数8  , 8大于7 ,同理删去此列 。

          剑指Offer_4_二维数组中的查找                 当前数2 ,小于7 , 此时列表加一,去除第一行 。

      剑指Offer_4_二维数组中的查找          当前数4 ,小于7 ,此时列表加一,去除第一行 。

      剑指Offer_4_二维数组中的查找          当前数7 , 等于7 , 返回true。

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

c++ :

 #include<bits/stdc++.h>

 using namespace std ;

 int main()
{
int a[][] = {
{,,,},
{,,,},
{,,,},
{,,,},
} ;
int n ;
cin >> n ; // 要查找的元素
int i= ;
int j= ;
while((i<=)&&(j>=)){
if(a[i][j]>n){
j-- ;
}else if(a[i][j]<n){
i++ ;
}else if(a[i][j]==n){
cout << "yes" <<endl ;
break ;
}
}
return ;
}

Java:

 import java.util.Scanner;

 public class Find {
public static void main(String[] args) {
int a[][] = {
{1, 2, 8, 9},
{2, 4, 9, 12},
{4, 7, 10, 13},
{6, 8, 11, 15},
};
int n ;
Scanner cin = new Scanner(System.in) ;
n = cin.nextInt() ;
int i=0 ;
int j=a.length - 1;
while((i<=3)&&(j>=0)){
if(a[i][j]>n){
j-- ;
}else if(a[i][j]<n){
i++ ;
}else if(a[i][j]==n){
System.out.println("yes");
break ;
}
}
}
}
           
 
上一篇:Python3面向对象—点和矩形类


下一篇:win32自绘按钮,使用GDI+(三)