js算法--搜索二维矩阵 II和计算右侧小于当前元素的个数

末蓝、 2022-12-22 04:40 144阅读 0赞

### 搜索二维矩阵 II ###

编写一个高效的算法来搜索 m x n 矩阵 matrix 中的一个目标值 target。该矩阵具有以下特性：

每行的元素从左到右升序排列。 每列的元素从上到下升序排列。

### 实例 ###

现有矩阵 matrix 如下： 
    [ 3
    	[1, 4, 7, 11, 15], 
    	[2, 5, 8, 12, 19], 
    	[3, 6, 9, 16, 22], 
    	[10, 13, 14, 17, 24], 
    	[18, 21, 23, 26, 30] 
    ] 
    给定 target = 5，返回 true。 
    给定 target = 20，返回 false。

### 方案1 ###

#### 暴力法 ####

#### 思路 ####

题目只需找出二维数组中是否包含目标值，因此直接用两个 for 循环遍历二维矩阵的所有元素，找到目标元素则返回 true，遍历完仍未找到则返回 false。

#### 详解 ####

1.  第一层 for 循环取到二维数组中所有的一维数组
2.  第二层 for 循环中用两个索引值取到二维数组中每一个具体的值
3.  将取到的每一个值和目标值作比较，若相同则返回 true
4.  若直到所有循环结束还未找到与目标值相同的值则返回 false

### 方案二 ###

#### 思路 ####

由于矩阵的行和列是排序的，从左到右递增，从上到下递增，所以对任意元素和目标值比较大小时，总可以去找相对较小（往左往上）或相对较大（往右往下）的值继续比较，直到找到目标值或找不到。

#### 详解 ####

1.  直接取二维数组中左下角的值和目标值比较
2.  若该值比目标值大，则向上查找（第一个索引减 1），若该值比目标值小，则向右查找（第二个索引加 1）
3.  重复该操作，当查询值等于目标值时则返回 true
4.  若直到查询值离开二维数组时还未找到目标值则返回 false