leetcode
leetcode 2001 ~ 2050
优质数对的数目

优质数对的数目

难度:

标签:

题目描述

代码结果

运行时间: 80 ms, 内存: 32.1 MB


/*
 * 思路:
 * 1. 使用流操作遍历数组中的每一个数对 (num1, num2)。
 * 2. 计算 num1 OR num2 和 num1 AND num2 的结果,并计算二进制中 1 的个数。
 * 3. 过滤掉不满足 k 条件的数对,并计数。
 */

import java.util.stream.IntStream;

public int countGoodPairsStream(int[] nums, int k) {
    int n = nums.length;
    return (int) IntStream.range(0, n).boxed()
        .flatMap(i -> IntStream.range(i, n)
            .filter(j -> Integer.bitCount(nums[i] | nums[j]) + Integer.bitCount(nums[i] & nums[j]) >= k)
            .mapToObj(j -> new int[] {nums[i], nums[j]}))
        .count();
}

解释

方法:

该题解的思路是首先对数组去重,然后统计每个数字的二进制表示中1的个数,用Counter来计数各个位数的数字出现的次数。之后,遍历Counter的每一对位数(i, j),如果两者之和大于等于k,则说明这两个位数的数字组合成的数对满足条件,应该将它们出现的次数相乘,并累加到结果中。

时间复杂度:

O(n^2)

空间复杂度:

O(n)

代码细节讲解

🦆
在算法实现中,为什么首先选择对数组进行去重操作?去重对最终结果的计算有何影响?
去重操作是为了确保每个数字在最终的统计中只被计算一次。如果不进行去重,同一个数字的重复出现会导致其二进制中1的个数被多次计算,从而影响最终计数器(Counter)中各个位数的计数结果。这会导致在计算满足条件的数对时,重复数字的贡献被错误地放大,从而得到一个不准确的结果。因此,通过去重,我们能确保每个数字对应的位数只被统计一次,这有助于正确计算满足条件的数对总数。
🦆
在题解中提到,遍历Counter的每一对位数(i, j)时,只有当i + j >= k时才计算数对。这是否意味着对于i + j < k的情况,这些位数的数对可以完全忽略不计?
是的,题解的逻辑中确实指出只有当两个位数的和大于等于k时,这两个位数对应的数字组合才被认为是优质数对,因此符合要求。对于i + j < k的情况,这些数对的位数和不满足给定的阈值k,因此它们可以被忽略不计。这是基于题目条件设定的,即只有位数和满足或超过k的数对才被视为有效,从而减少不必要的计算和提高算法效率。
🦆
算法中对Counter中的每一对(i, u)和(j, v)进行了遍历,这是否能确保统计的每一对数字都是独一无二的数对?如果(i, u)和(j, v)相同,这种情况在计算中如何处理?
在算法中,遍历Counter确实会遇到(i, u)和(j, v)相同的情况,即当i等于j时。在这种情况下,我们依然需要计算这样的数对,但是计算方式略有不同。对于i等于j的情况,实际上是在计算同一个位数的数字组合,因此应该计算的是这个位数数字出现次数的平方,即u * u。但是,如果直接这样计算会导致每个组合被计算两次(一次为(i, j),一次为(j, i)),因此需要特殊处理以避免重复计算。一种常见的处理方式是在计算时只考虑i <= j的情况,并在i = j时按u * u处理,而在i < j时按u * v处理。

相关问题