作者推荐
本文涉及的基础知识点
题目
给你一个下标从 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 <= 105
1 <= nums[i] <= 109
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; } };
。也就是我们常说的专业的人做专业的事。 |
|如果程序是一条龙，那算法就是他的是睛|
测试环境
操作系统：win7 开发环境： VS2019 C++17
或者 操作系统：win10 开发环境：
VS2022 C++17
