搜索二维矩阵

### 1. 要求

判断在 m * n 矩阵中，是否存在一个目标值。该矩阵具有如下特性：每行中的整数从左到右按升序排,每行的第一个整数大于前一行的最后一个整数。

### 2. 示例

#### 2.1 正确示例

> 输入：matrix = [ [1,3,5,7],[10,11,16,20],[23,30,34,60] ], target = 3
输出：true

#### 2.2 错误示例

> 输入：matrix = [ [1,3,5,7],[10,11,16,20],[23,30,34,60] ], target = 13
输出：false

### 3. 思路与实现

#### 3.1 解法一

记录每个元素出现的次数。以每个元素值作为key，出现次数作为value，最后匹配与target相等的key，value>=1即返回true。

<div class="code-toolbar"><pre class="language-javascript line-numbers"><code class="language-javascript">function searchMatrix(matrix, target) {
        return matrix.reduce((acc,cur)=>{
            cur.forEach(item =>{
                acc[item] = (acc[item] || 0 ) + 1;
            });
            return acc
        },{})[target] >= 1
    }</code></pre></div>

* 时间复杂度：O(n^2)
* 空间复杂度：O(n^2)

#### 3.2 解法二

将后面的数组拼接到前一个数组的尾部，再对拼接后的数组使用二分查找。难点在于确认中点元素所在的行，以及所在该行的位置。示意图：

![](https://images.xxzxka.com/typecho/mat.jpg)

<div class="code-toolbar"><pre class="language-javascript line-numbers"><code class="language-javascript">function searchMatrix(matrix, target) {
        //矩阵行数和列数
        let row = matrix.length;
        let col = matrix[0].length;
        //开始索引和结束索引
        let start = 0;
        let end = row * col - 1;
        while (start <= end){
            let midIndex = Math.floor((end -start) / 2) + start;
            //先确定中点位置索引所在的行;中点索引midIndex除以每行的长度col的结果向下取整:matrix[Math.floor(midIndex / col)]
            //再确定中点位置索引在该行的位置;中点索引midIndex对每行的长度col取模:midIndex % col
            let midElement = matrix[Math.floor(midIndex / col)][midIndex % col];

if (target < midElement){
                end--
            }else if (target > midElement){
                start++
            }else{
                return true
            }
        }
        return false
    }</code></pre></div>

- 时间复杂度：O(log m*n)
- 空间复杂度：O(1)

本文由 yuin 创作，
本站文章除注明转载/出处外，均为本站原创或翻译，转载前请务必署名。