leetcode
leetcode 1901 ~ 1950
统计可以被 K 整除的下标对数目

统计可以被 K 整除的下标对数目

难度:

标签:

题目描述

代码结果

运行时间: 95 ms, 内存: 27.1 MB


/*
 * 题目思路:
 * 1. 使用 Java Stream 遍历数组的所有可能的下标对 (i, j),其中 i < j。
 * 2. 对于每一对 (i, j),计算 nums[i] * nums[j]。
 * 3. 使用 filter 函数过滤出乘积能被 k 整除的对。
 * 4. 计算这些对的数量。
 */
import java.util.stream.IntStream;

public class Solution {
    public int countPairs(int[] nums, int k) {
        return (int) IntStream.range(0, nums.length)
                .boxed()
                .flatMap(i -> IntStream.range(i + 1, nums.length)
                        .filter(j -> (nums[i] * nums[j]) % k == 0)
                        .mapToObj(j -> new int[]{i, j}))
                .count();
    }
}

解释

方法:

本题解采用了数学和哈希表的方法来优化解决问题。首先用哈希表freq统计数组中每个元素与k的最大公因数(gcd)出现的频次。然后对这个哈希表中的元素(gcd值及其出现次数)进行排序。对于每一对gcd值,如果它们的乘积能被k整除,则表示存在多个满足条件的下标对(i, j),即这两个gcd值对应的原数组元素组合的所有可能。对于相同的gcd值,需要使用组合数公式来计算可能的下标对数。通过这种方法,将问题转化为了较少数量的gcd值的组合问题,从而避免了直接的n^2复杂度的暴力解法。

时间复杂度:

O(u^2 + u log u + n log k)

空间复杂度:

O(u)

代码细节讲解

🦆
为什么在处理计数时要使用最大公因数(gcd)而不是直接考虑nums[i]和nums[j]的乘积?
直接考虑 nums[i] 和 nums[j] 的乘积会导致时间复杂度过高,特别是当数组长度较大时。使用最大公因数(gcd)的方法可以将问题简化。如果 nums[i] 和 nums[j] 的乘积能被 k 整除,那么 nums[i] 和 nums[j] 与 k 的 gcd 乘积也一定能被 k 整除。这样通过先计算每个数与 k 的 gcd,再处理这些 gcd 的乘积,可以有效减少需要处理的数据量和复杂度。
🦆
题解中提到了使用bisect_left进行查找,这种查找方法的目的是什么?如何确保它能找到正确的位置?
bisect_left 函数在 sorted list 中用于找到插入位置以维护列表顺序。它能快速找到第一个大于或等于指定元素的位置。在这个题解中,使用 bisect_left 是为了快速找到能与当前 gcd 值相乘并能被 k 整除的另一个 gcd 的起始位置。它确保能找到正确的位置,因为数组已经被排序,bisect_left 依赖于这个顺序来进行二分查找,从而快速定位到正确的开始位置。
🦆
在处理相同gcd值的组合情况时,为什么可以使用组合数公式c[i][1] * (c[i][1] - 1) // 2来计算下标对数?
当两个下标 i 和 j 指向的元素具有相同的 gcd 值时,任选两个不同的下标组成的对都满足条件。因此,问题可以转化为如何从频次为 c[i][1] 的集合中选择两个不同元素的组合数。这可以通过组合数公式 C(n, 2) = n*(n-1)/2 来计算,其中 n 是具有相同 gcd 的元素的数量。
🦆
在题解中,排序操作是如何影响整体算法性能的?为什么选择排序这些gcd值?
排序操作主要影响算法性能,因为它具有 O(N log N) 的时间复杂度,其中 N 是不同 gcd 值的数量。排序是必须的,因为它保证了后续使用二分查找(bisect_left)的有效性和正确性。通过排序,可以确保在查找合适的 gcd 组合时,数组是有序的,这是二分查找算法的前提条件。排序后,可以有效地通过索引快速访问和比较元素,从而提高算法的整体效率和性能。

相关问题