本文准备讲解1个算法编程问题, 这个算法编程问题来自LintCode平台。不了解.LintCode平台的读者可以阅读笔者文章(在线编程平台推荐-LeetCode)。问题的英文版本描述如下:
Search a 2D Matrix II
Write an efficient algorithm that searches an m x n matrix, return the occurrence count of targets.
This matrix has the following properties:
Integers in each row are sorted from left to right.
Integers in each column are sorted from up to bottom.
Example
Consider the following matrix:
[
[1, 3, 5, 7],
[2, 4, 7, 8],
[3, 5, 9, 10]
]
Given target =3, return 2.
搜索二维矩阵 II
搜索m×n矩阵。
这个矩阵具有以下特性:
Integers in each row are sorted from left to right.
Integers in each column are sorted from up to bottom.
样例
考虑下列矩阵:
[
[1, 3, 5, 7],
[2, 4, 7, 8],
[3, 5, 9, 10]
]
给出 target =3,返回 2.
面对2维矩阵,首先需要找到目标元素所在的矩阵行。每个矩阵行都为升序数列,矩阵的首列也为升序数列。找到目标元素所在的矩阵行需要搜索矩阵首列。然后需要找到目标元素所在的位置。找到目标元素所在的矩阵位置需要搜索目标元素所在的矩阵行。JAVA 语言提供的数组搜索函数只能找到目标数组元素。面对本问题,找到目标元素所在的矩阵行不能选用 JAVA 语言提供的数组搜索函数;找到目标元素所在的矩阵位置可以选用 JAVA 语言提供的数组搜索函数。该算法不能处理行内字符重复出现。 ( 参见另1个问题的文章:LintCode问题图解-20。 )
搜索二维矩阵 II 问题和搜索二维矩阵问题都不能对应通用的搜索二维矩阵问题,通用的搜索二维矩阵问题需要选用更多的测试用例。