【题目描述】
Write an efficient algorithm that searches for a value in an m x n matrix.
This matrix has the following properties:Integers in each row are sorted from left to right.The first integer of each row is greater than the last integer of the previous row.
写出一个高效的算法来搜索 m × n矩阵中的值。
这个矩阵具有以下特性：每行中的整数从左到右是排序的。每行的第一个数大于上一行的最后一个整数。
【题目链接】
【题目解析】
对于这个给定的矩阵，我们如果用brute force解法，用两个嵌套循环，O(n2)便可以得到答案.但是我们需要注意的是这道题已经给定了这个矩阵的两个特性，这两个特性对于提高我们算法的时间复杂度有很大帮助，首先我们给出一个O(n)的解法，也就是说我们可以固定住右上角的元素，根据递增或者递减的规律，我们可以判断这个给定的数值是否存在于这个矩阵当中.
【参考答案】
评论
发表评论