笔试题分析-1

93 阅读 0 评论 62 点赞

我是靠谱客的博主聪明香烟，最近开发中收集的这篇文章主要介绍笔试题分析-1，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

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

思路：在大多数面试题目中，固定思路就是先想这道题符合哪种数据结构，大多数是栈，队列，链表什么的。就是先确定一个固定框架，至于细节则是根据题目慢慢分析了。粗看这道题，题目并不难，当然作为笔试题，解法越多，耗时越短为好。

一种解法为：观察这个二维数组的结构，从左到右递增，从上到下递增，理所应当，第一列最下端是一个比较合适的起始位置，这个还是比较容易理解的，如果target比之小，则向右移，如果target比之大，则向上移。

 1 public class Solution {
 2     public boolean Find(int target, int [][] array) {
 3         int a = array.length;
 4         int b = array[0].length;
 5         int i,j;
 6         for(i=a-1,j=0;i>=0&&j<b;){
 7             if(target==array[i][j])
 8             {
 9                 return true;  
10             }
11             if(target<array[i][j]){
12                 i--;
13                 continue;
14             }
15             if(target>array[i][j]){
16                 j++;
17                 continue;
18             }
19         }return false;
20  
21     }
22 }

第二种解法：反正是找数，直接暴力遍历呗，当然效率低一些，但不能说这不是一种解法。。。这种就不写代码了。。

第三种解法：可以考虑二分查找，因为每一行都是有序的，可以对每一行使用二分查找，这是没有问题的，反正比直接遍历快。。代码如下：

 1 public class Solution {
 2     public boolean Find(int [][] array,int target) {
 3          
 4         for(int i=0;i<array.length;i++){
 5             int low=0;
 6             int high=array[i].length-1;
 7             while(low<=high){
 8                 int mid=(low+high)/2;
 9                 if(target>array[i][mid])
10                     low=mid+1;
11                 else if(target<array[i][mid])
12                     high=mid-1;
13                 else
14                     return true;
15             }
16         }
17         return false;
18  
19     }
20 }