2354-优质数对的数目

Raphael Liu Lv10
  2023-09-13 00:47:26 2023-09-13 00:47:26 Created   2023-09-13 16:06:30 2023-09-13 16:06:30 Updated    

给你一个下标从 0 开始的正整数数组 nums 和一个正整数 k 。

如果满足下述条件，则数对 (num1, num2) 是 优质数对 ：

  • num1 和 num2 都 在数组 nums 中存在。
  • num1 OR num2 和 num1 AND num2 的二进制表示中值为 1 的位数之和大于等于 k ，其中 OR 是按位 或 操作，而 AND 是按位 与 操作。

返回 不同 优质数对的数目。

如果 a != c 或者 b != d ，则认为 (a, b) 和 (c, d) 是不同的两个数对。例如，(1, 2) 和 (2, 1) 不同。

注意： 如果 num1 在数组中至少出现 一次 ，则满足 num1 == num2 的数对 (num1, num2)
也可以是优质数对。

示例 1：

**输入：** nums = [1,2,3,1], k = 3
**输出：** 5
**解释：** 有如下几个优质数对：
- (3, 3)：(3 AND 3) 和 (3 OR 3) 的二进制表示都等于 (11) 。值为 1 的位数和等于 2 + 2 = 4 ，大于等于 k = 3 。
- (2, 3) 和 (3, 2)： (2 AND 3) 的二进制表示等于 (10) ，(2 OR 3) 的二进制表示等于 (11) 。值为 1 的位数和等于 1 + 2 = 3 。
- (1, 3) 和 (3, 1)： (1 AND 3) 的二进制表示等于 (01) ，(1 OR 3) 的二进制表示等于 (11) 。值为 1 的位数和等于 1 + 2 = 3 。
所以优质数对的数目是 5 。

示例 2：

**输入：** nums = [5,1,1], k = 10
**输出：** 0
**解释：** 该数组中不存在优质数对。

提示：

  • 1 <= nums.length <= 105
  • 1 <= nums[i] <= 109
  • 1 <= k <= 60

本题 视频讲解 已出炉，额外讲解了如何用集合论来思考二进制。欢迎点赞三连，在评论区分享你对这场周赛的看法~

提示 1

对于 x|y 和 x&y，在同一个比特位上，如果都有 1，那这个 1 会被统计两次；如果一个为 1 另一个为 0，那这个 1 会被统计一次。

提示 2

例如 x=110，y=011，只统计一次的部分为 x’=100，y’=001，统计了两次的部分为 x&y=010。我们可以直接把 010 重新分配到 x’ 和 y’ 上，这样又得到了 x 和 y。

记 c(x) 为 x 的二进制表示中的 1 的个数，则有如下等式：

c(x|y)+c(x&y)=c(x)+c(y)

另外一种思路是把二进制数看成集合，根据容斥原理 |A \cup B| = |A| + |B| - |A \cap B|，得

|A \cup B| + |A \cap B| = |A| + |B|

再转换到二进制上，同样可以得到上面的等式。

提示 3

遍历去重后的 nums，统计 c(\textit{nums}[i]) 的个数，记录在 cnt 中，然后写一个二重循环遍历 cnt，对于所有的 c(x)+c(y)\ge k，累加 cnt}[c(x)]\cdot\textit{cnt}[c(y)]，表示从这两组中各选一个 x 和 y 组成优质数对的个数（乘法原理）。

复杂度分析

  • 时间复杂度：O(n+U^2)，其中 n 为 nums 的长度，U 为不同的 c(\textit{nums}[i]) 的个数，不超过 30。
  • 空间复杂度：O(n+U)。
[sol1-Python3]
1
2
3
4
5
6
7
8
9
class Solution:
    def countExcellentPairs(self, nums: List[int], k: int) -> int:
        cnt = Counter(x.bit_count() for x in set(nums))
        ans = 0
        for cx, ccx in cnt.items():
            for cy, ccy in cnt.items():
                if cx + cy >= k:  # (x,y) 是优质数对
                    ans += ccx * ccy
        return ans
[sol1-Java]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    public long countExcellentPairs(int[] nums, int k) {
        var vis = new HashSet<Integer>();
        var cnt = new HashMap<Integer, Integer>();
        for (var x : nums)
            if (vis.add(x)) {
                var c = Integer.bitCount(x);
                cnt.put(c, cnt.getOrDefault(c, 0) + 1);
            }
        var ans = 0L;
        for (var x : cnt.entrySet())
            for (var y : cnt.entrySet())
                if (x.getKey() + y.getKey() >= k)
                    ans += (long) x.getValue() * y.getValue();
        return ans;
    }
}
[sol1-C++]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    long long countExcellentPairs(vector<int> &nums, int k) {
        unordered_map<int, int> cnt;
        for (int x : unordered_set<int>(nums.begin(), nums.end())) // 去重
            ++cnt[__builtin_popcount(x)];
        long ans = 0L;
        for (auto &[cx, ccx] : cnt)
            for (auto &[cy, ccy] : cnt)
                if (cx + cy >= k) // (x,y) 是优质数对
                    ans += (long) ccx * ccy;
        return ans;
    }
};
[sol1-Go]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
func countExcellentPairs(nums []int, k int) (ans int64) {
	vis := map[int]bool{}
	cnt := map[int]int{}
	for _, x := range nums {
		if !vis[x] {
			vis[x] = true
			cnt[bits.OnesCount(uint(x))]++
		}
	}
	for cx, ccx := range cnt {
		for cy, ccy := range cnt {
			if cx+cy >= k { // (x,y) 是优质数对
				ans += int64(ccx) * int64(ccy)
			}
		}
	}
	return
}

进一步地，二重循环可以用前缀和（或者后缀和）来优化。

我们可以从小到大遍历 cnt}[c(x)]，由于 c(y)\ge k-c(x)，c(y) 也会从大到小减小，我们可以用后缀和维护这些 cnt}[c(y)] 的和。

复杂度分析

  • 时间复杂度：O(n+U)，其中 n 为 nums 的长度，U=30。
  • 空间复杂度：O(n+U)。
[sol2-Python3]
1
2
3
4
5
6
7
8
9
10
11
12
class Solution:
    def countExcellentPairs(self, nums: List[int], k: int) -> int:
        cnt = [0] * 30
        for x in set(nums):
            cnt[x.bit_count()] += 1
        ans = 0
        s = sum(cnt[k:])
        for cx, ccx in enumerate(cnt):
            ans += ccx * s
            if 0 <= k - 1 - cx < 30:
                s += cnt[k - 1 - cx]
        return ans
[sol2-Java]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    static final int U = 30;

    public long countExcellentPairs(int[] nums, int k) {
        var vis = new HashSet<Integer>();
        var cnt = new int[U];
        for (var x : nums)
            if (vis.add(x)) ++cnt[Integer.bitCount(x)];
        var ans = 0L;
        var s = 0;
        for (var i = k; i < U; ++i)
            s += cnt[i];
        for (var cx = 0; cx < U; ++cx) {
            ans += (long) cnt[cx] * s;
            var cy = k - 1 - cx;
            if (0 <= cy && cy < U) s += cnt[cy];
        }
        return ans;
    }
}
[sol2-C++]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    static constexpr int U = 30;
public:
    long long countExcellentPairs(vector<int> &nums, int k) {
        int cnt[U] = {};
        for (int x : unordered_set<int>(nums.begin(), nums.end())) // 去重
            ++cnt[__builtin_popcount(x)];
        long ans = 0L;
        int s = 0;
        for (int i = k; i < U; ++i)
            s += cnt[i];
        for (int cx = 0; cx < U; ++cx) {
            ans += (long) cnt[cx] * s;
            int cy = k - 1 - cx;
            if (0 <= cy && cy < U) s += cnt[cy];
        }
        return ans;
    }
};
[sol2-Go]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
func countExcellentPairs(nums []int, k int) (ans int64) {
	const U = 30
	vis := map[int]bool{}
	cnt := [U]int{}
	for _, x := range nums {
		if !vis[x] {
			vis[x] = true
			cnt[bits.OnesCount(uint(x))]++
		}
	}
	s := 0
	for i := k; i < U; i++ {
		s += cnt[i]
	}
	for cx, ccx := range cnt {
		ans += int64(ccx) * int64(s)
		cy := k - 1 - cx
		if 0 <= cy && cy < U {
			s += cnt[cy]
		}
	}
	return
}
 Comments
On this page
2354-优质数对的数目