如何用ES6高阶函数优化最小公倍数求解代码以避免超时？

问题背景 #

原代码在处理较大数值范围时会出现超时，要求仅使用ES6高阶函数进行优化。原代码如下：

function smallestCommons(arr) {
  // Return the Smallest Common Multiple for pair of Input Numbers.
  
  const [min, max] = arr.sort((a,b)=>a-b); 
  // Sorting Input Array to give min and max values for the range

  const range = Array(max-min+1).fill(0).map((_,i)=>i+min);
  // Initialize the Array

  let prodAll = range.reduce((product,number)=>product*number);
  // Finding the product of all numbers which is a gauranteed multiple of the range


  let res = Array(prodAll/max).fill(0).map((_,i)=>(i+1)*max) // Initialize an Array of all the multiples of the 'max' number upto 'prodAll'
                            .find(mulp=>range.every((val)=>mulp%val===0)); // check if any number meets the divisiblable criteria sooner then 'prodAll'
        

  return res;
}

console.log(smallestCommons([1,13]))

原代码问题分析 #

原代码的核心问题是生成了超大范围的倍数数组：当数值范围较大时，prodAll（所有数的乘积）会呈阶乘级增长，比如[1,13]的乘积是6227020800，生成包含4.7亿个元素的数组不仅内存占用极高，遍历检查的效率也极低，直接导致超时。

优化方案（基于ES6高阶函数） #

利用最小公倍数的递推性质：多个数的最小公倍数可以通过依次计算两两数的LCM（最小公倍数）递推得到，而两两数的LCM可通过GCD（最大公约数）计算：LCM(a,b) = (a*b) / GCD(a,b)。结合ES6的reduce高阶函数实现递推，完全避免生成超大数组。

优化后的代码：

function smallestCommons(arr) {
  // 排序得到范围的最小值和最大值
  const [min, max] = arr.sort((a, b) => a - b);
  // 生成数值范围数组
  const range = Array(max - min + 1).fill(0).map((_, idx) => idx + min);

  // 欧几里得算法求最大公约数（GCD）
  const gcd = (a, b) => b === 0 ? a : gcd(b, a % b);
  // 计算两个数的最小公倍数（LCM）
  const lcm = (a, b) => (a * b) / gcd(a, b);

  // 用reduce递推计算整个范围的最小公倍数
  return range.reduce((currentLCM, num) => lcm(currentLCM, num));
}

console.log(smallestCommons([1,13])); // 输出360360

优化说明 #

1. 效率提升：时间复杂度从原代码的O(NM)（N为倍数数量，M为范围长度）降至O(Mlog(max))，其中log(max)是欧几里得算法的时间复杂度，处理大范围数值时不会出现超时。
2. ES6特性使用：使用了箭头函数、解构赋值、reduce、map等ES6高阶函数和语法，符合要求。
3. 内存优化：不再生成超大倍数数组，内存占用大幅降低。

内容的提问来源于stack exchange，提问作者Areeb Hussain Qureshi