leetcode-888-公平的糖果交换

时间:2021-08-11 16:10:44

题目描述:

爱丽丝和鲍勃有不同大小的糖果棒: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。