给你印象最深的一道面试题是什么?


欢迎在本帖子下,写上你遇到过的令你印象最深刻的一道面试题。
已邀请:

July - 抠细节抠体验,不妥协不将就。

赞同来自: lianyutao Rachel lijinma hiluluke 石头头头 joice_cd 薇酱更多 »


刚毕业那会,面过不少公司,没看到什么好的面试题。
稍有点印象的是杨氏矩阵查找。

在一个m行n列的二维数组中,每一行都按照从左到右递增的顺序排列,每一列都按照从上到下递增的顺序排列。现输入这样的一个二维数组和一个整数,请完成一个函数,判断数组中是否含有该整数。
例如给定如下图所示的二维数组,它的每一行、每一列都递增排序。如果在这个数组中查找数字6,则返回true;如果查找数字5,则由于该数组不含有数字5,返回false。
1.png

虽然后来知道这题有两种解法:
解法一:分治法
以查找数字6为例,因为矩阵的行和列都是递增的,所以整个矩阵的对角线上的数字也是递增的,故我们可以在对角线上进行二分查找:如果要找的数的大小介于对角线上相邻的两个数之间,则可以排除掉左上和右下的两个小矩形,而在左下和右上的两个小矩形内继续递归查找。如下图所示:
2.png

解法二:定位法
如下图所示,首先直接定位到矩阵中最右上角的元素,如果这个元素比要找的数6大就往左走,比要找的数6小就往下走,直到找到要找的数字6为止。这个方法的时间复杂度是O(m+n)。
3.png

但当时确实没有想到解法二。

要回复问题请先登录注册

返回顶部