Skip to content

Latest commit

 

History

History
183 lines (129 loc) · 9.25 KB

284.精读《算法题 - 统计可以被 K 整除的下标对数目》.md

File metadata and controls

183 lines (129 loc) · 9.25 KB

今天我们看一道 leetcode hard 难度题目:统计可以被 K 整除的下标对数目。

题目

给你一个下标从 0 开始、长度为 n 的整数数组 nums 和一个整数 k ,返回满足下述条件的下标对 (i, j) 的数目:

  • 0 <= i < j <= n - 1
  • nums[i] * nums[j] 能被 k 整除。

示例 1:

输入:nums = [1,2,3,4,5], k = 2
输出:7
解释:
共有 7 对下标的对应积可以被 2 整除:
(0, 1)、(0, 3)、(1, 2)、(1, 3)、(1, 4)、(2, 3) 和 (3, 4)
它们的积分别是 2、4、6、8、10、12 和 20 。
其他下标对,例如 (0, 2) 和 (2, 4) 的乘积分别是 3 和 15 ,都无法被 2 整除。  

思考

首先想到的是动态规划,一个长度为 n 的数组结果与长度为 n-1 的关系是什么?

首先 n-1 时假设算好了一个结果 result,那么长度为 n 时,新产生的匹配是下标 [0, n-1] 与下标 n 数字的匹配关系,假设这些关系中有 q 个满足题设,则最终答案是 result + q

这种想法适合 (i, j) 满足任意关系的题目,代码如下:

function countPairs(nums: number[], k: number): number {
  if (nums.length < 2) {
    return 0
  }

  const dpCache: Record<number, number> = {}

  for (let i = 1; i < nums.length; i++) {
    switch (i) {
      case 1:
        if (nums[0] * nums[1] % k === 0) {
          dpCache[1] = 1    
        } else {
          dpCache[1] = 0
        }
        break
      default:
        // [0,i-1] 洗标范围内与 i 下标组合,看看有多少种可能
        let currentCount = 0
        for (let j = 0; j <= i - 1; j++) {
          if (nums[j] * nums[i] % k === 0) {
            currentCount++
          }
        }
        dpCache[i] = dpCache[i - 1] + currentCount
    }
  }

  return dpCache[nums.length - 1]
};

很可惜超时了,因为回头想想,虽然思路是 dp,但本质上是暴力解法,时间复杂度是 O(n²)。

为了 AC,必须采用更低复杂度的算法。

利用最大公约数解题

如果只循环一次数组,那么必须在循环到数组每一项的时候,就能立刻知道该项与其他哪几项的乘积符合 nums[i] * nums[j] 能被 k 整除,这样的话累加一下就能得到答案。

也就是说,拿到数字 nums[i]k,我们要知道有哪些 nums[j] 是满足要求的。

当然,如果把所有剩余数字循环一遍来找满足条件的 nums[j],那时间复杂度就还是 O(n²),但不循环似乎无法继续思考了,这道题很容易在这里陷入僵局。

接下来就要发散思维了,先想这个问题:满足条件的 nums[j] 要满足 nums[i] * nums[j] % k === 0,那除了通过遍历把每一项 nums[j] 拿到真正的算一遍之外,还有什么更快的办法呢?

除了真的算一下之外,想想 nums[j] 还要具备什么特性?这个特性最好和倍数有关,因为如果我们计算所有数字倍数出现的个数,时间复杂度会比较低。

nums[i]k 的最大公约数就满足这个条件,因为我们希望的是 nums[j] * nums[i]k 的倍数,那么 nums[j] 最小的值就是 k / nums[i],但这个除出来可能不是整数,那必须保证 k 除以的数字是一个整数,这个除数用 nums[i]k 的最大公约数最划算。nums[j] 可以更大,只要是这个结果的倍数就行了,总结一下,nums[j] 要满足是 k / gcd(nums[i], k) 的倍数。

再重点解释下原因,我们假设 nums[i] = 2, k=100,此时是 k 比较大的情况,那么其最大公约数一定小于等于 nums[i],因此 k / 最大公约数 * nums[j] 得到的数字一定大于 k / nums[i] * nums[j],毕竟最大公约数比 nums[i] 小嘛,而 k / nums[i] * nums[j] 就是不考虑 nums[j] 是整数情况下让 k 可以整除 nums[i] * nums[j] 时,nums[j] 取的最小值的情况,因此 nums[j] 只要是 k / 最大公约数 的倍数就行了。

反之,如果 k 比 nums[i] 小,比如 nums[i] = 100, k=2,此时最大公约数是小于等于 k 的,但用一个比 k 还要大的 nums[i] 作为乘法的一边,乘出来的结果肯定大于 k,所以不用担心 nums[i] * nums[j] < k 的情况,所以 nums[j] 只要是 k / 最大公约数 的倍数就行了。

综上,无论如何 nums[j] 只要是 k / 最大公约数 的倍数就行了。

所以对于每一个 nums[i],我们能快速计算出 x = k / gcd(nums[i], k),接下来只要找到 nums 所有数字中,是 x 倍数的有多少累加起来就行了。这一步也不能鲁莽,因为数组长度非常大,性能更好的方案是:先从1开始到最大值,计算出每个数字的倍数有几个,存在一个 map 表里,之后找倍数有几个直接从 map 表里获取就行了

比如有数字 1 ~ 10,我们要计算每个数字的倍数出现了几次,大概是这么算的:

  • 1,2,3... 数到 10,那么 1 的倍数有 10 个数字。
  • 2,4,6,8,10 数 5 次,那么 2 的倍数有 5 个数字。
  • 3,6,9 数 3 次,那么 3 的倍数有 3 个数字。

以此类推,我们发现一个规律,即对于长度为 n 的数组,要数的总次数为 n + n/2 + n/3 + ... + 1,这是一个调和数列,具体怎么证明的笔者已经忘了,但可以记住它的值趋向于欧拉常数 + ln(n+1),这就是要数的次数,所以用这个方案,整体时间复杂度是 O(nlnn),比 O(n²) 小了很多。

所以我们只要 “暴力” 的从 1 开始到 nums 最大的数字,把所有数字的倍数都提前计算出来,最后的时间复杂度反而会更小,这是非常神奇的结论。为了避免计算多余的倍数关系,反而时间复杂度是 O(n²),而暴力计算所有数字倍数的时间复杂度竟然是 O(nlnn),这个可以背下来。

接下来就简单了,直接上代码。

用 js 实现 gcd(最大公约数)计算可以用辗转相除法:

function gcd(left: number, right: number) {
    return right === 0 ? left : gcd(right ,left % right)
}

整体代码实现:

function countPairs(nums: number[], k: number): number {
    // nums 最大的数字
    let max = 0
    nums.forEach(num => max = Math.max(num, max))

    // Map<数字x, 数字x 倍数在 nums 中出现的次数>
    const mutipleMap: Record<number, number> = {}

    // 先遍历一次 nums,将其倍数次自增
    nums.forEach(num => {
        if (mutipleMap[num] === undefined) {
            mutipleMap[num] = 1
        } else {
            mutipleMap[num]++
        }
    })

    // 按以下规律数倍数出现的次数,但忽略自身
    // 1,2,3...,max
    // 2,4,6...,max
    // 3,6,9...,max
    for (let i = 1; i <= max; i++) {
        for (let j = i * 2; j <= max; j+=i) {
            if (mutipleMap[i] === undefined) {
                mutipleMap[i] = 0
            }
            mutipleMap[i] += mutipleMap[j] ?? 0
        }
    }

    // 答案
    let result = 0

    // k / gcd(num, k) 的数组出现的次数累加
    nums.forEach(num => {
        const targetMutiple = k / gcd(num, k)
        result += mutipleMap[targetMutiple] ?? 0
    })

    // 排除自己乘以自己满足条件的情况
    nums.forEach(num => {
        if (num * num % k === 0) { result-- }
    })
    
    return result / 2
};

有几个注意要点。

第一个是 for (let j = i * 2,之所以要乘以 2,是因为在前面遍历 nums 时,自己的倍数已经被算过一次,比如 3,6,9 的 3 已经被初始化算过一次,所以从 3*2=6 开始就行了。

第二个是 mutipleMap[i] += mutipleMap[j],比如 i=3,j=9 时,因为 9 是 3 的倍数,所以此时 3 的倍数可以继承 9 的倍数的数量,而数字是不断变大的,所以不会重复。

第三个是 if (num * num % k === 0) { result-- },因为题目要求 0 <= i < j <= n - 1,但我们计算倍数时,比如 9 是 3 的倍数,但 9 可以通过 3 * 3 得到,这种不合规的数据要过滤掉。

第四个是 return result / 2,因为在最后累加次数时,把每个数字与其他数字都判断了一遍,假设 1, 3 是合法的,那么 3, 1 也肯定是合法的,但因为 i < j 的要求,我们要把 3, 1 干掉,所有合法的结果都存在顺序颠倒的 case,所以除以 2.

总结

这道题很容易栽在动态规划超时的坑上面,要解决此题需要跨越两座大山:

  1. 想到最大公约数与另一个数字之间的关系。
  2. 意识到暴力计算倍数的时间复杂度是 O(nlnn)。

最后,本题还隐含了 n + n/2 + n/3 + ... + 1 为什么极限是 O(nlnn) 的知识,背后有一个 调和数列 的大知识背景,感兴趣的同学可以深入了解。

讨论地址是:精读《算法 - 统计可以被 K 整除的下标对数目》· Issue #495 · dt-fe/weekly

如果你想参与讨论,请 点击这里,每周都有新的主题,周末或周一发布。前端精读 - 帮你筛选靠谱的内容。

版权声明:自由转载-非商用-非衍生-保持署名(创意共享 3.0 许可证