【二分查找】LeetCode:2354.优质数对的数目

作者推荐

贪心算法LeetCode2071:你可以安排的最多任务数目

本文涉及的基础知识点

二分查找算法合集

题目

给你一个下标从 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 <= 10⁵
1 <= nums[i] <= 10⁹
1 <= k <= 60

分析

时间复杂度

O(nlogn)，枚举数对的第二个数，时间复杂度O(n)；二分查找第一个数的数量，O(logn)。

原理

如果有重复的数，删除。假定存在b1等于b2，那么任意数对(a,b1)是优质数对，则(a,b2)也是优质数对，故可以删除b1。
c=a&b d = c|b 。c和d 二进制1的数量之和，就是a和b 二进制1的数量之和
去重后，对于任意b， (x,b)都不会重复，因为x不会相等。setNum中的任意数，都可以是x，包括自己。
我们只关心a和b中1的数量，不关心a和b的值。所以枚举vBitCount。

代码

核心代码

//通过 x &= (x-1)实现
int bitcount(unsigned x) {
int countx = 0;
while (x) {
countx++;
x &= (x - 1);
}
return countx;
}

int bitcount(unsigned long long x) {
int countx = 0;
while (x) {
countx++;
x &= (x - 1);
}
return countx;
}

class Solution {
public:
	long long countExcellentPairs(vector<int>& nums, int k) {
		std::unordered_set<int> setNum(nums.begin(), nums.end());
		vector<int> vBitCount;
		for (const auto& n : setNum)
		{
			vBitCount.emplace_back(bitcount((unsigned long long)n));
		}
		sort(vBitCount.begin(), vBitCount.end());
		long long llRet = 0;
		for (const auto& n : vBitCount)
		{
			llRet += vBitCount.end() - std::lower_bound(vBitCount.begin(), vBitCount.end(), k - n);
		}
		return llRet;
	}
};

测试用例

template
void Assert(const vector& v1, const vector& v2)
{
if (v1.size() != v2.size())
{
assert(false);
return;
}
for (int i = 0; i < v1.size(); i++)
{
assert(v1[i] == v2[i]);
}
}

template
void Assert(const T& t1, const T& t2)
{
assert(t1 == t2);
}

int main()
{
vector nums;
int k;
long long res;
{
Solution slu;
nums = { 1, 2, 3, 1 }, k = 3;
auto res = slu.countExcellentPairs(nums, k);
Assert(5LL, res);
}
{
Solution slu;
nums = { 5,1,1 }, k = 10;
auto res = slu.countExcellentPairs(nums, k);
Assert(0LL, res);
}
//CConsole::Out(res);
}

2023年3月版

//通过 x &= (x-1)实现
int bitcount(unsigned x) {
int countx = 0;
while (x) {
countx++;
x &= (x - 1);
}
return countx;
}

class Solution {
public:
long long countExcellentPairs(vector& nums, int k) {
std::sort(nums.begin(), nums.end());
nums.erase(std::unique(nums.begin(), nums.end()), nums.end());
std::vector vOneBitNums;
for (const auto& n : nums)
{
vOneBitNums.push_back(bitcount(n));
}
std::sort(vOneBitNums.begin(), vOneBitNums.end());
int iSameNum = vOneBitNums.end() - std::lower_bound(vOneBitNums.begin(), vOneBitNums.end(), (k + 1) / 2);
long long iNotSameNum = 0;
for (int i = 0; i < vOneBitNums.size(); i++)
{
auto itEnd = vOneBitNums.begin() + i;
iNotSameNum += itEnd - std::lower_bound(vOneBitNums.begin(), itEnd, k - vOneBitNums[i]);
}
return iSameNum + iNotSameNum * 2;
}
};