题目描述:
爱丽丝和鲍勃有不同大小的糖果棒:A[i]
是爱丽丝拥有的第 i
块糖的大小,B[j]
是鲍勃拥有的第 j
块糖的大小。
因为他们是朋友,所以他们想交换一个糖果棒,这样交换后,他们都有相同的糖果总量。(一个人拥有的糖果总量是他们拥有的糖果棒大小的总和。)
返回一个整数数组 ans
,其中 ans[0]
是爱丽丝必须交换的糖果棒的大小,ans[1]
是 Bob 必须交换的糖果棒的大小。
如果有多个答案,你可以返回其中任何一个。保证答案存在。
示例 1:
输入:A = [1,1], B = [2,2]
输出:[1,2]
示例 2:
输入:A = [1,2], B = [2,3]
输出:[1,2]
示例 3:
输入:A = [2], B = [1,3]
输出:[2,3]
示例 4:
输入:A = [1,2,5], B = [2,4]
输出:[5,4]
提示:
1 <= A.length <= 10000
1 <= B.length <= 10000
1 <= A[i] <= 100000
1 <= B[i] <= 100000
- 保证爱丽丝与鲍勃的糖果总量不同。
- 答案肯定存在。
要完成的函数:
vector<int> fairCandySwap(vector<int>& A, vector<int>& B)
说明:
1、这道题给定两个vector,A和B,两个vector中存储的都是int类型的数据,这些数据表示A和B两个人拥有的糖果大小。
比如A=[1,2,5],B=[2,4],表示A有大小为1、大小为2和大小为5的糖果,B有大小为2和大小为4的糖果。
现在想让A和B拥有的糖果总量一样多,让他们各自交换一个糖果。
比如上面这个例子,就可以A交出5,B交出4,变成[1,2,4]和[2,5],这样糖果总量就一样多了。
返回A交出的糖果大小和B交出的糖果大小,以vector的形式返回。
这道题目保证有答案,可能有多个答案,只需要返回其中任意一个。
2、这道题难道要一一尝试交换,比较交换之后的糖果总量会不会相等?
应该没有必要这样做。
考虑到最终两个人的糖果总量相等,那么可以计算出最终这个相等的总量是多少。
比如1中的例子,A的总量是8,B的总量是6,那么平均下来每个人应该是7。
那么接下来就要在A中找到一个元素比B中某个元素大1的,逐个对比,可以发现交换5和4就可以达成目标。
其中逐个对比这个部分,难道我们要做一个双重循环吗?也没有必要。
我们先做一个升序排序,接着就是两个指针在A中和B中不断地移动就可以了。
代码如下:(附详解)
vector<int> fairCandySwap(vector<int>& A, vector<int>& B)
{
sort(A.begin(),A.end());//升序排序
sort(B.begin(),B.end());//升序排序
int sum1=0,sum2=0,sum3,cha,cha1;
for(int i:A)//sum1存储A中的总量
sum1+=i;
for(int i:B)//sum2存储B中的总量
sum2+=i;
sum3=(sum1+sum2)/2;//sum3是平均值
cha=sum1-sum3;//cha表示A和平均值之间的差,如果大于0,说明A要在B中找一个小cha这个数值的,如果小于0,同理
int i=0,j=0;
while(i<A.size()&&j<B.size())//i和j两个索引不断地向后走
{
cha1=A[i]-B[j];
if(cha1==cha)//如果刚好等于,那么返回两个数值
return {A[i],B[j]};
else if(cha1<cha)//如果小于,那么说明A[i]数值太小,应该更大一点
i++;
else //如果大于,那么说明B[j]数值太小,应该更大一点
j++;
}
}
上述代码实测76ms,beats 81.67% of cpp submissions。