算法_搜索二维矩阵&分解质因数

搜索二维矩阵

难度：简单

描述：

写出一个高效的算法来搜索 m × n 矩阵中的值。

这个矩阵具有以下特性：

1. 每行中的整数从左到右是从小到大排序的。
2. 每行的第一个数大于上一行的最后一个整数。

样例：

[
  [1, 3, 5, 7],
  [10, 11, 16, 20],
  [23, 30, 34, 50]
]

给出 target = 3，返回 true

题目分析：

双循环找出是否有这个值，根据第二个特性，我们可以跳过一些第二层循环，算法更具效率。

代码：

/**
 * @param matrix: matrix, a list of lists of integers
 * @param target: An integer
 * @return: a boolean, indicate whether matrix contains target
 */
const searchMatrix = function(matrix, target) {
  for (let key of matrix.keys()) { // 遍历外层数组
    let value = matrix[key]; // 拿到每行元素
    // 判断target是否在当前行中，跳过其他不必要循环
    if (target <= value[value.length - 1]) { 
      for (let item of value.keys()) { // 遍历行中元素 
        if (target === value[item]) { // 找到值
          return true;
        } else if (target < value[item]) {  // 值超过target即找不到(因为是排序的)
          return false;
        }
      }
    }
  }
  return false;  // 没有找到即返回false
};

---

分解质因数

难度：简单

质因数的定义：

能整除给定正整数的质数。

百度百科：质因数

描述：

1. 将一个整数分解为若干质因数之乘积
2. 你需要从小到大排列质因子

样例：

• 给出 10, 返回 [2, 5]
• 给出 660, 返回 [2, 2, 3, 5, 11]

题目分析：

从小到大排列质因子，需要将同一个质因子整除干净。

比如：20 可以被 2 整除两次。

提示：需要两层循环。

代码：

// 分解质因数
const primeFactorization = function(num) {
  let res = [];
  // 不需要判定i是否为质数，如果i不为质数，且能整除num时，num早被i的因数所除。故能整除num的i必是质数。
  // i * i > num 退出循环 num一开始会在第二层循环被i整除成比较小的数字
  for (let i = 2; i * i <= num; i++) {
    while (num % i === 0) {
      // 直到有余数退出循环
      num = num / i; // 改变num
      res.push(i); // 没有余数 能整除 这一步会找出所有质因数 不会出现4的那种情况
    }
  }
  if (num !== 1) res.push(num); // num到最后也是质因数
  return res;
};