LeetCode 954. 二倍数对数组（map计数）
LeetCode 954. 二倍数对数组（map计数）
Michael阿明
发布于 2021-02-19 15:30:08
发布于 2021-02-19 15:30:08
代码可运行
运行总次数：0
代码可运行
文章目录
1. 题目
给定一个长度为偶数的整数数组 A，只有对 A 进行重组后可以满足 对于每个 0 <= i < len(A) / 2，都有 A[2 * i + 1] = 2 * A[2 * i] 时，返回 true；否则，返回 false。
示例 1：
输入：[3,1,3,6]
输出：false
示例 2：
输入：[2,1,2,6]
输出：false
示例 3：
输入：[4,-2,2,-4]
输出：true
解释：我们可以用 [-2,-4] 和 [2,4] 这两组组成 [-2,-4,2,4] 或是 [2,4,-2,-4]
示例 4：
输入：[1,2,4,16,8,4]
输出：false
提示：
0 <= A.length <= 30000
A.length 为偶数
-100000 <= A[i] <= 100000来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/array-of-doubled-pairs 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
2. 解题
- map计数，检查 每个元素的2倍 或者 偶数的一半 是否存在
class Solution {
public:
bool canReorderDoubled(vector<int>& A) {
map<int,int> m;
for(int a : A)
m[a]++;
int count = 0, a, c;
for(auto it = m.begin(); it != m.end(); ++it)
{
a = it->first;
if(m.count(2*a) && m[2*a] > 0)//两倍的数存在
{
if(a != 0)
c = min(m[2*a], m[a]);
else// a == 0
c = m[a]/2;
count += 2*c;
m[a] -= c;
m[2*a] -= c;
}
if(a%2==0 && m.count(a/2) && m[a/2] > 0)//是偶数，且一半存在
{
if(a != 0)
c = min(m[a/2], m[a]);
else
c = m[a]/2;
count += 2*c;
m[a] -= c;
m[a/2] -= c;
}
}
return count == A.size();
}
};276 ms 53.7 MB
or 下面的写法思路更清晰
class Solution {
public:
bool canReorderDoubled(vector<int>& A) {
map<int,int> m;
for(int a : A)
m[a]++;
int count = 0, a;
for(auto it = m.begin(); it != m.end(); ++it)
{
a = it->first;
if(it->second == 0)
continue;
if(a < 0)
{
if(a&1)//负奇数，不能匹配
return false;
m[a/2] -= m[a];
if(m[a/2] < 0)//个数不够不能匹配
return false;
}
else if(a == 0)
{
if(m[a]&1)//0 奇数个，不能匹配
return false;
}
else // (a > 0)
{
m[2*a] -= m[a];
if(m[2*a] < 0)//个数不够不能匹配
return false;
}
}
return true;
}
};236 ms 54 MB
本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。
原始发表：2020/09/30 ，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录
腾讯云开发者
