leetcode 2354. Number of Excellent Pairs (python)

攜手創作,共同成長！這是我參與「掘金日新計劃 · 8 月更文挑戰」的第4天,點擊查看活動詳情

描述

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 and num2 exist in the array nums.
• The sum of the number of set bits in num1 OR num2 and num1 AND num2 is greater than or equal to k, where OR is the bitwise OR operation and AND 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.
復制代碼

Note:

1 <= nums.length <= 10^5
1 <= nums[i] <= 10^9
1 <= k <= 60
復制代碼

解析

根據題意,給定一個 0 An array of positive integers of indices nums 和一個正整數 k .Returns the number of distinct pairs of outstanding numbers. 如果滿足以下條件,a pair of numbers (num1, num2) excellent：

• 數字 num1 和 num2 are present in the array nums 中.
• num1 OR num2 和 num1 AND num2 結果中 1 的個數大於等於 k ,其中 OR 為按位或運算,AND 為按位與運算.

This question is about finding the rules,我們計算 3 和 5 The bitwise OR and bitwise AND operations of ：

9 5 or and
1 0 1 0
0 1 1 0
0 0 0 0
1 1 1 1
復制代碼

From the above, it can be found that the operation required in the question can be converted into the binary representation of two numbers 1 的個數之和.我們先將 set(nums) Each type of number in calculates its own binary representation 1 的個數,Then we count it as counter ,counter 中的 key 是可能出現的 1 的個數,value Indicates that it can appear in binary 1 的個數為 key The number of distinct decimal digits of .Because we are looking for different pairs of numbers,所以我們只要對 counter different keys i 和鍵 j 進行兩兩比較,如果 i+j 大於等於 k ,Then the explanation satisfies the meaning of the question,There are different pairs of numbers that we can form counter[i] * counter[j] 個,加入到結果 result 中即可.

函數 c The time complexity is basically constant level,Most of the time is spent on the double loop,時間復雜度為 O(N^2) ,空間復雜度為 O(N) .

解答

class Solution(object):
def countExcellentPairs(self, nums, k):
""" :type nums: List[int] :type k: int :rtype: int """
def c(n):
result = 0
while n != 0:
n &= n-1
result += 1
return result
s = set(nums)
counter = collections.Counter(c(n) for n in s)
result = 0
for i in counter:
for j in counter:
if i + j >= k:
result += counter[i] * counter[j]
return result
復制代碼

運行結果

56 / 56 test cases passed.
Status: Accepted
Runtime: 1488 ms
Memory Usage: 31.7 MB
Submitted: 0 minutes ago
復制代碼

原題鏈接

leetcode.com/contest/wee…

您的支持是我最大的動力