这几天在Iteye看到有个有奖问答的题目,二维数组的二分查找。想想最近也没什么事情,就做了一下。自己的算法基础很是薄弱,所以也参考了一些网上的东东。那个有奖什么就不参加了。哈哈。。。。
原题如下(估计很多人知道了):
在一个二维数组中,每一行都按照从左到右递增的顺序排序,每一列都按照从上到下递增的顺序排序。请完成一个函数,输入这样的一个二维数组和一个整数,判断数组中是否含有该整数。
例如下面的二维数组就是每行、每列都递增排序。如果在这个数组中查找数字7,则返回true;如果查找数字5,由于数组不含有该数字,则返回false。
我这里主要讲下我当时是怎么做的
。
我的第一印象如果想快速的查找的话应该要利用到对角线。因为对角线元素在他所在的矩阵中最大的,可以在一定程度缩小查找范围。但当时没有具体想清楚该怎么做。后来又想到题目中没有指定数组是N*N的,所以先放弃了这个想法。然后继续想想,如果面试官问我这个题目的话该怎么做。
首先当然是保证不错,二重遍历是肯定不会错的。我都一个一个比较了还会有什么问题呢。当然这个就跟别人问你用什么方法排序的,你回答冒泡排序一样,没什么技术含量。不过至少说明你了解了题目的内容。
再深入一下,二维数组是数组的数组。一般对于有序数组可以采用二分法对数组进行一个lgn的查找。那这样可以对二维数组的每个数组进行一次二分查找。这样就比较不错了,知道了二分查找。估计可以打个及格的分数了。
继续深入,可能就会像我一样想到了利用对角线。但是这个要考虑到不是N*N的情况。利用对角线对矩阵分块,然后就可以排除一些数据了。类如上图中,查找元素 7.跟对角线元素比较之后, 4 < 7 < 10, 那就说明,4左上角,10右下角的数据不用处理。就减少了一半的数据。这篇文章很清楚的说明了这种方法应该怎么做。
http://justjavac.iteye.com/blog/1310178
做到这一步以后,我是没什么办法了。如果面试官问我,还有更好的办法没。我就只能拜拜了。不过,好的方法总是有的,只要好好的寻找。我在网上搜索的时候发现了杨氏矩阵查找的方法。
http://blog.csdn.net/michealmeng555/article/details/2489923
杨氏矩阵查找跟对角线的方法差不多,但是不是用的主对角线\,而是用的副对角线/. 在副对角线中的元素有个性质。在以他为左右两个顶点的矩阵中,他是一个数组中的最大值,是另外一个数组中的最小值。那我们可以利用这个性质,假设我们选择最右上角的元素 a。那么对于需要查找的元素b,如 a > b 向左走,如果 a < b向下走。直到到达最左下角结束。真是太精妙了。
其实这些算法都不是很难,难的是能够想到。如果没想到,那就尽快的学起来吧。。。
public class Search2Array {
private static int[][] arrays = {{1,2,8,9},{2,4,9,12},{4,7,10,13},{6,8,11,15}};
//最容易的办法,使用两重循环
//复杂度O(n2)
public static boolean search1(int target){
for(int[] arr : arrays){
for(int a : arr){
if (a == target){
return true;
}
}
}
return false;
}
//对每个子一维数组用二分查找
//复杂度为O(nlgn)
public static boolean search2(int target){
boolean flag = false;
for(int [] arr : arrays){
flag = binarySearch(arr, 0, arr.length -1, target);
if(flag){
return true;
}
}
return false;
}
//二分查找
private static boolean binarySearch(int[] array, int start, int end, int target){
int middle = start + (end - start)/2;
while(start <= end){
if(array[middle] == target){
return true;
}else if(array[middle] > target){
end = middle - 1;
}else {
start = middle + 1;
}
middle = start + (end - start)/2;
}
return false;
}
//使用最右上角或者最左下角的元素作为起始元素
//这两个位置的元素有个性质:是一个数组中最大的,也是一个数组中最小的
//纵向也看做一个数组
//复杂度为O(m+n)
public static boolean youngTableau(int target){
int raw = 0;
int col = arrays[0].length - 1;
while(col >= 0 && raw <= arrays.length -1){
int tmp = arrays[raw][col];
if( tmp == target){
return true;
}else if(tmp > target) {
col--;
}else{
raw++;
}
}
return false;
}
public static void main(String[] args){
System.out.println(search1(7));
System.out.println(search1(5));
System.out.println(search2(7));
System.out.println(search2(5));
System.out.println(youngTableau(7));
System.out.println(youngTableau(5));
}
}
- 大小: 6.4 KB
分享到:
相关推荐
用C++语音实现一维数组二维数组写入txt,从txt中读取数据存到一维数组、二维数组,数组用指针表示
一维数组转二维数组
二维数组中的查找,逐行扫描,行内使用二分查找。最差情况需要扫描所有行,待完善
C# json 一维数组 和 二维数组的转换 写的非常详细,对大家有帮助
// 二维数组冒泡排序 public static void main(String[] args) { int i=0, j=0, temp = 0; int[][] nums1 = { { 34, 1, 22, 5 }, { 28, 98, 15, 32 }, { 33, -5, 17, 41 } }; int rows = nums1.length; //二维...
将labview内二维数组方便的转化为一维数组使用
CStringArray二维数组CStringArray二维数组CStringArray二维数组CStringArray二维数组CStringArray二维数组CStringArray二维数组CStringArray二维数组CStringArray二维数组
通过vue解析表头合并的表格,后台返回的数据格式为[{name:aa,list:[{value:100}]}] 通过table与v-for组合循环数据达到目的。 vue 表头合并数据解析 vue 二维数组解析 vue 二维list解析 vue table+v-for
C语言程序设计-求出二维数组周边元素之和,作为函数值返回;二维数组的值在主函数中赋予;
二维数组中的查找,jupter
labview读取二维数组中所有数据,涉及到labview中数组VI的熟练使用。
VB.NET二维数组快速排序(更新) 'OldArrays(),为排序二维数组;NewArrays(),为存放结果数组,SortColumnsOrOrders(),传递排序参数数组,偶数个为排序列号,奇数为升降序,0为升序,1为降序;FieldRow,是否有字段行...
介绍了数组、一维数组、二维数组、多维数组及其应用示例
二维数组的声明和使用ppt介绍很快可以上手练习和理解用的
用二维数组实现二维矩阵的加法和乘法 #include #define SIZE 4 void addMatrix(int [ ][SIZE], int [ ][SIZE], int [ ][SIZE]); void mulMatrix(int [ ][SIZE], int [ ][SIZE], int [ ][SIZE]); void ...
程序功能:从三维数组中提取出任意二维的数据,并保存在新的二维矩阵中,且能所以变换顺序。
c#调用c++DLL,DLL里是二维数组 ,c#里如何调用二维数组
labview 删除二维数组全空行
读BMP位图的像素到二维数组,二维数组是动态申请的。将读入的二维数组中的像素显示出来,看是否与原图相符合,并且将像素点的值写入data.txt文本文档
实现一个“可变长二维数组”,这个二维数组的行数可由输入决定,每行的元素个数仍可由输入决定。每个数组元素值都是1. 执行结果如下: 请输入行数: 5 请输入第1行的元素个数: 20 请输入第2行的元素个数: 34 请...