作者推荐

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

本文涉及的基础知识点

二分查找算法合集

LeetCode2354.优质数对的数目

给你一个下标从 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;
	}
};

• 1
• 2
• 3
• 4
• 5
• 6
• 7
• 8
• 9
• 10
• 11
• 12
• 13
• 14
• 15
• 16
• 17
• 18

测试用例

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;
}
};

扩展阅读

视频课程

有效学习：明确的目标 及时的反馈 拉伸区（难度合适），可以先学简单的课程，请移步CSDN学院，听白银讲师（也就是鄙人）的讲解。
https://edu.csdn.net/course/detail/38771

如何你想快

速形成战斗了，为老板分忧，请学习C#入职培训、C++入职培训等课程
https://edu.csdn.net/lecturer/6176

相关下载

想高屋建瓴的学习算法，请下载《喜缺全书算法册》doc版
https://download.csdn.net/download/he_zhidan/88348653

。也就是我们常说的专业的人做专业的事。 |
|如果程序是一条龙，那算法就是他的是睛|

测试环境

操作系统：win7 开发环境： VS2019 C++17
或者 操作系统：win10 开发环境：

VS2022 C++17