Skip to content
On this page

笛卡尔积

时间复杂度 O(3)

js
console.time('start')
const arr = [['128G', '256G'], ['红色', '黑色'], ['plus', 'common']]
function descartes(list) {
  return list.reduce((prev, next) => {
    let res = []
    prev.forEach((prevItem) => {
      next.forEach((nextItem) => {
        // 第一次遍历时x1为空数组[],[...prevItem, nextItem] 会返回[nextItem],即[ [ '128G' ], [ '256G' ] ], prevItem被忽略,而不是返回[undefined, nextItem]
        // 第二次及后面遍历则从128G+红色、128G+黑色依次遍历...
        res.push([...prevItem, nextItem])
      })
    })
    console.log(res)
    return res
  }, [[]])
}

console.log(descartes(arr))
console.timeEnd('start') // 10ms±
// O(3) 思路
/*
  使用reduce遍历获取当前项 和 下一项
  初始化result为length为1的二维数组。方便遍历第一个规格,结果为: [ [ '128G' ], [ '256G' ] ]
  第二次及后面循环时,往res里第一个规格里push新的array即可
*/
console.time('start')
const arr = [['128G', '256G'], ['红色', '黑色'], ['plus', 'common']]
function descartes(list) {
  return list.reduce((prev, next) => {
    let res = []
    prev.forEach((prevItem) => {
      next.forEach((nextItem) => {
        // 第一次遍历时x1为空数组[],[...prevItem, nextItem] 会返回[nextItem],即[ [ '128G' ], [ '256G' ] ], prevItem被忽略,而不是返回[undefined, nextItem]
        // 第二次及后面遍历则从128G+红色、128G+黑色依次遍历...
        res.push([...prevItem, nextItem])
      })
    })
    console.log(res)
    return res
  }, [[]])
}

console.log(descartes(arr))
console.timeEnd('start') // 10ms±
// O(3) 思路
/*
  使用reduce遍历获取当前项 和 下一项
  初始化result为length为1的二维数组。方便遍历第一个规格,结果为: [ [ '128G' ], [ '256G' ] ]
  第二次及后面循环时,往res里第一个规格里push新的array即可
*/

时间复杂度 O(2)