思考-《剑指offer》题之二维数组查找

书中从矩阵的一个边角(如右上角出发),开始查找某数值m,找到后打印m所在的矩阵中位置。假设某一时刻,这时来到了某位置(i,j),如果Data(i,j)<m,将j+1,如果是等于,则m的位置已经找到了;如果大于,则将i+1。按照这样的方式,能够每次减少一行或一列,直到找到目标。这是一道通过比较的方式,查找相应元素的算法。

我想到了两个问题。

  1. 如果出发时把位置设置在中间,会不会比从右上角快些?
  2. 如果所比较的数值m换成了序列,如(x(i),y(i))、甚至是三变量(x(i),y(i),z(i)),那还如何从目标中找到答案?

问题一:
如果设置在了中间,那么Data(i,j)<m时,应该向数值递增的右边或下边进行查找,反之,小于则向上边或左边进行查找。虽然每次比较貌似需要比较2次,但是由于处于中间的位置,所以工作量减为1/2。而位于矩阵一角,工作量多一倍,每次比较一次,所以速度应该是一样的(时间复杂度)
问题二:
如果是二变量序列,可以先比较x(i),再比较y(i),多变量序列也是从首位变量到末尾变量的依次比较。这里把二维变量想象成二维平面上,每次比较必然能够移动一格。如果是三维变量则作为立方体,每次比较也必然能够移动一格。结合问题一,在这里,问题已经变了,因为每次只需要比较一次,所以应该从中间开始找,这样能够保证平均情况下工作量是从边界开始的方式的1/2。
(注:这里类比成二维平面、三维立方,并不是说相邻序列其中一个是另一个的某个变量加一或减一这样的关系。仅仅指的是它们严格按照递增、递减的规律。一个区域弄成“实心”、“满”(内部没有空白元素)的这样一种状态)

最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容

  • 1. Java基础部分 基础部分的顺序:基本语法,类相关的语法,内部类的语法,继承相关的语法,异常的语法,线程的语...
    子非鱼_t_阅读 31,834评论 18 399
  • 背景 一年多以前我在知乎上答了有关LeetCode的问题, 分享了一些自己做题目的经验。 张土汪:刷leetcod...
    土汪阅读 12,790评论 0 33
  • 1.插入排序—直接插入排序(Straight Insertion Sort) 基本思想: 将一个记录插入到已排序好...
    依依玖玥阅读 1,290评论 0 2
  • 动态规划(Dynamic Programming) 本文包括: 动态规划定义 状态转移方程 动态规划算法步骤 最长...
    廖少少阅读 3,380评论 0 18
  • 初入F公司第一个月,我被派去上海参加培训。培训师是个日本人,全英文授课。那个矮小男人的日式发音虽让人抓狂,...
    不负小春阅读 13,525评论 3 2