Skip to content

Latest commit

 

History

History
179 lines (144 loc) · 4.7 KB

File metadata and controls

179 lines (144 loc) · 4.7 KB
comments difficulty edit_url rating source tags
true
困难
2075
第 303 场周赛 Q4
位运算
数组
哈希表
二分查找

English Version

题目描述

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

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

  • num1num2 在数组 nums 中存在。
  • num1 OR num2num1 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

解法

方法一

Python3

class Solution:
    def countExcellentPairs(self, nums: List[int], k: int) -> int:
        s = set(nums)
        ans = 0
        cnt = Counter()
        for v in s:
            cnt[v.bit_count()] += 1
        for v in s:
            t = v.bit_count()
            for i, x in cnt.items():
                if t + i >= k:
                    ans += x
        return ans

Java

class Solution {
    public long countExcellentPairs(int[] nums, int k) {
        Set<Integer> s = new HashSet<>();
        for (int v : nums) {
            s.add(v);
        }
        long ans = 0;
        int[] cnt = new int[32];
        for (int v : s) {
            int t = Integer.bitCount(v);
            ++cnt[t];
        }
        for (int v : s) {
            int t = Integer.bitCount(v);
            for (int i = 0; i < 32; ++i) {
                if (t + i >= k) {
                    ans += cnt[i];
                }
            }
        }
        return ans;
    }
}

C++

class Solution {
public:
    long long countExcellentPairs(vector<int>& nums, int k) {
        unordered_set<int> s(nums.begin(), nums.end());
        vector<int> cnt(32);
        for (int v : s) ++cnt[__builtin_popcount(v)];
        long long ans = 0;
        for (int v : s) {
            int t = __builtin_popcount(v);
            for (int i = 0; i < 32; ++i) {
                if (t + i >= k) {
                    ans += cnt[i];
                }
            }
        }
        return ans;
    }
};

Go

func countExcellentPairs(nums []int, k int) int64 {
	s := map[int]bool{}
	for _, v := range nums {
		s[v] = true
	}
	cnt := make([]int, 32)
	for v := range s {
		t := bits.OnesCount(uint(v))
		cnt[t]++
	}
	ans := 0
	for v := range s {
		t := bits.OnesCount(uint(v))
		for i, x := range cnt {
			if t+i >= k {
				ans += x
			}
		}
	}
	return int64(ans)
}