题目
——“优质数对的数目”
You are given a 0-indexed positive integer array nums
and a positive integer k
.
A pair of numbers (num1, num2)
is called excellent if the following conditions are satisfied:
- Both the numbers
num1
andnum2
exist in the arraynums
. - The sum of the number of set bits in
num1 OR num2
andnum1 AND num2
is greater than or equal tok
, whereOR
is the bitwise OR operation andAND
is the bitwise AND operation.
Return the number of distinct excellent pairs.
Two pairs (a, b)
and (c, d)
are considered distinct if either a != c
or b != d
. For example, (1, 2)
and (2, 1)
are distinct.
Note that a pair (num1, num2)
such that num1 == num2
can also be excellent if you have at least one occurrence of num1
in the array.
Example 1:
Input: nums = [1,2,3,1], k = 3 Output: 5 Explanation: The excellent pairs are the following: - (3, 3). (3 AND 3) and (3 OR 3) are both equal to (11) in binary. The total number of set bits is 2 + 2 = 4, which is greater than or equal to k = 3. - (2, 3) and (3, 2). (2 AND 3) is equal to (10) in binary, and (2 OR 3) is equal to (11) in binary. The total number of set bits is 1 + 2 = 3. - (1, 3) and (3, 1). (1 AND 3) is equal to (01) in binary, and (1 OR 3) is equal to (11) in binary. The total number of set bits is 1 + 2 = 3. So the number of excellent pairs is 5.
Example 2:
Input: nums = [5,1,1], k = 10 Output: 0 Explanation: There are no excellent pairs for this array.
Constraints:
1 <= nums.length <= 105
1 <= nums[i] <= 109
1 <= k <= 60
思路
题目大意是说,“优质数对”是bit_count(a&b) + bit_count(a|b) >= k的数对,求给定数组中“优质数对”的个数。
解题的关键在于,bit_count(a&b) + bit_count(a|b) = bit_count(a) + bit_count(b),想到这个性质,解题就非常轻松了。
对数组去重,按1的位数做分桶,遍历2个桶的组合求和即可。
代码
时间复杂度O(n),空间复杂度O(n)。
class Solution(object):
def countExcellentPairs(self, nums, k):
"""
:type nums: List[int]
:type k: int
:rtype: int
"""
def hammingWeight(n):
n = ((n & 0xaaaaaaaa) >> 1) + (n & 0x55555555)
n = ((n & 0xcccccccc) >> 2) + (n & 0x33333333)
n = ((n & 0xf0f0f0f0) >> 4) + (n & 0x0f0f0f0f)
n = ((n & 0xff00ff00) >> 8) + (n & 0x00ff00ff)
n = ((n & 0xffff0000) >> 16) + (n & 0x0000ffff)
return n
N = 32
cnt = [0] * N
for n in set(nums):
cnt[hammingWeight(n)] += 1
ret = 0
for i in range(N):
for j in range(N):
if i + j >= k:
ret += cnt[i] * cnt[j]
return ret
AC,收工。

——此处是内容的分割线——
除非注明,否则均为广陌原创文章,转载必须以链接形式标明本文链接
本文链接:https://www.utopiafar.com/2022/07/25/leetcode-2354-number-of-excellent-pairs/
码字不易,如果觉得内容有帮助,欢迎留言or点赞!