编写一个高效的算法来搜索 m x n 矩阵 matrix 中的一个目标值 target。该矩阵具有以下特性:
每行的元素从左到右升序排列。 每列的元素从上到下升序排列。
示例
现有矩阵 matrix 如下:[[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。
思路
题目只需找出二维数组中是否包含目标值,因此直接用两个 for 循环遍历二维矩阵的所有元素,找到目标元素则返回 true,遍历完仍未找到则返回 false。
详解
第一层 for 循环取到二维数组中所有的一维数组
第二层 for 循环中用两个索引值取到二维数组中每一个具体的值
将取到的每一个值和目标值作比较,若相同则返回 true
若直到所有循环结束还未找到与目标值相同的值则返回 false
代码
const searchMatrix = function (matrix, target) {for (let i = 0; i < matrix.length; i++) {for (let j = 0; j < matrix[i].length; j++) {if (matrix[i][j] === target) {return true;}}}return false;};
复杂度分析
时间复杂度: 通过遍历二维矩阵的所有元素来寻找它所对应的目标元素,这将耗费 的时间。
空间复杂度:
思路
由于矩阵的行和列是排序的,从左到右递增,从上到下递增,所以对任意元素和目标值比较大小时,总可以去找相对较小(往左往上)或相对较大(往右往下)的值继续比较,直到找到目标值或找不到。
详解
直接取二维数组中左下角的值和目标值比较
若该值比目标值大,则向上查找(第一个索引减 1),若该值比目标值小,则向右查找(第二个索引加 1)
重复该操作,当查询值等于目标值时则返回 true
若直到查询值离开二维数组时还未找到目标值则返回 false
代码
const searchMatrix = function (matrix, target) {let j = matrix.length - 1;let i = 0;while (j >= 0 && i < matrix[0].length) {if (matrix[j][i] > target) {j--;} else if (matrix[j][i] < target) {i++;} else {return true;}}return false;};
复杂度分析
时间复杂度: 由于行只能运算 m 次,列只能运算 n 次,是两个变量之和,这将耗费 的时间。
空间复杂度: 用到了两个变量,其空间复杂度为
给定一个整数数组 nums,按要求返回一个新数组 counts。数组 counts 有该性质: counts[i]
的值是 nums[i]
右侧小于 nums[i]
的元素的数量。
示例
输入: [5,2,6,1]输出: [2,1,1,0]解释:5 的右侧有 2 个更小的元素 (2 和 1).2 的右侧仅有 1 个更小的元素 (1).6 的右侧有 1 个更小的元素 (1).1 的右侧有 0 个更小的元素.
思路
暴力法很简单,遍历每个元素 x,并遍历查找在其后边并且比它小的元素,进行累加,最后将统计出来的个数 push 到新开辟的数组中。
详解
算法流程:
声明一个数组用来存储最后的结果;
第一层循环用来遍历所有的元素;
循环体内先声明一个变量,初始值为 0,用来记录当前元素右边并且比当前元素小的个数;
接下来通过第二个循环来计算当前元素右边比它小的数,由于只需要计算它右边的数,所以第二个循环从第 i + 1 开始,遍历到数组的最后一个值即可。第二层循环体内通过 if 语句来判断比当前元素小的数,然后执行 num ++;
代码
const countSmaller = (nums) => {const newArr = [];for (let i = 0, len = nums.length; i < len; i += 1) {let num = 0;for (let j = i + 1; j < nums.length; j += 1) {if (nums[j] < nums[i]) {num += 1;}}newArr.push(num);}return newArr;};
复杂度分析
时间复杂度: 对于每个元素,通过遍历数组的其余部分来寻找它所对应的目标元素,所以时间复杂度为 。
空间复杂度: 额外开辟了一个数组来存放结果,所以空间复杂度为 。
思路
首先将数组元素进行从小到大的排序,排序完成后,遍历原数组,找出原数组中当前元素在排序后的数组中的数组下标,即为该元素右侧比它小的个数,然后将排序后的数组中的这个元素删除。
例如: 原数组 nums = [5,2,6,1]; 排序后的数组为 newArr = [1,2,5,6]; 对原数组 nums 进行遍历,首先是元素 5,在 newArr 中其数组下标为 2,其右侧比它小的元素有2个;然后将 newArr 中的5这个元素删除,newArr = [1,2,6];接下来是元素2,在newArr中的下标为1,然后将 newArr 中的2这个元素删除,其右侧比它小的元素有1个;以此类推...
详解
算法流程:
将原数组从小到大排序,并声明一个新数组来存储;
声明一个数组用来存储最后的结果;
对原数组进行遍历;
通过数组的方法 indexOf 找到遍历的当前元素在排序后的数组中的位置,并赋值给变量index,该变量的值即为当前元素右侧比它小的个数;
通过数组的方法 splice ,把当前元素从原数组中删除;
代码
const countSmaller = (nums) => {const newArr = [...nums].sort((a, b) => a - b);const result = [];nums.forEach((n) => {const index = newArr.indexOf(n);result.push(index);newArr.splice(index, 1);});return result;};
复杂度分析
时间复杂度: 代码中 sort 函数的时间复杂度为 ,for 循环的时间复杂度为 ,因此整体的时间复杂度为 。
空间复杂度: 申请了 2 个大小为 n 的数组空间,因此空间复杂度为 。