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

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