问题:有一个数字矩阵,矩阵的每行从左到右是递增的,矩阵从上到下是递增的,请编写程序在这样的矩阵中查找某个数字是否存在。 要求:时间复杂度小于O(N);
杨氏矩阵普及:杨氏矩阵是对组合表示理论和舒伯特演算很有用的工具。它提供了一种很方便的方式来描述对称和一般线性群表示,并研究它们的性质。
分析:对于杨氏矩阵老说,右上角和左下角的元素是有特点的。右上角的元素是一行中最大的,一列中最小的。左下角的元素是一行中最小的,是一列中最大的。所以我们可以从右上角或者左下角开始查找。比如(线性搜索方法):从右上角开始查找的时候,右上角的元素比我们要查找元素小,我们就可以去掉右上角元素所在的这一行;右上角的元素比我们要查找的元素大,我们就可以去掉右上角元素所在的这一列。然后依然找右上角的元素继续和要查找的元素与比较。这样每一次比较去掉一行或者去掉一列。这个查找效率是高于遍历数组元素的,所以时间复杂度是小于O(N),也满足题目要求。
代码:
代码:
标签:右上角,元素,矩阵,查找,杨氏,一列 From: https://blog.51cto.com/u_15830263/6007627