题目描述
A[i] 是爱丽丝拥有的第 i 根糖果棒的大小,B[j] 是鲍勃拥有的第 j 根糖果棒的大小。交换一个,然后让他俩各自有的总大小相等。
算法 $O(n)$
class Solution {
public:
vector<int> fairCandySwap(vector<int>& A, vector<int>& B) {
int sum_A = 0, sum_B = 0;
for (int& a: A) // for (int i = 0; i < A.size(); i++)
sum_A += a;
for (int& b: B)// for (int i = 0; i < B.size(); i++)
sum_B += b;
int df_x = (sum_A - sum_B) / 2; //Defn定义总和差。 这题实际就是利用 公平交换等价于<=> a[i] - b[j] == (sumA-sumB)/2原理. 即交换后差改变两次。<=>一次差就等于总值差减半。
sort(A.begin(), A.end());
sort(B.begin(), B.end());
int i = 0, j = 0;
vector<int> ans;
while (i < A.size() && j < B.size()){
if (A[i] - B[j] == df_x){ //A[i] - B[j] 即dx 交换这一次的差。
ans.push_back(A[i]); //注lc官方题解中用了(unordered_set)类似哈希表 A[i]其实也等于B[j] + df(x) 可用这个来在A里找A.count(B[j] +df_x)
ans.push_back(B[j]);
break;
}
else if (A[i] - B[j] > df_x) j++;
else i++;
}
return ans;
}
};
单独写一下双指针逻辑:
如果df_x差值为正:A比B大,A就要换给B一个大数,相对应的B就给A换过来一个小数。
如果我们遍历到的A[i] - B[j] 比这个差值大,那么就说明 B[j]小了 j++
剩下情况便是A[i] - B[j]比这个差值小,那么说明A[i]小了,i++.
注:++是因为已经sort过,大的在后面,且每项均为正数(非负数也行其实--即对于++的逻辑原理,要求是非递减序列,当然其中应有递增片段,不然还遍历个啥..数都一样的话)
反过来一样,
如果df_x差值为负 < 0:B比A大,B就要换给A一个大数,相对应的A就给B换过来一个小数。
如果我们遍历到的A[i] - B[j] (这是个小于0的数) 比这个差值大,那么就说明 B[j]小了,需要多减一点(减一个更大的B[j],让它负的多一点,负的刚好为差值为止(从数轴负无穷处往差值逼近)) j++.
剩下情况便是A[i] - B[j]比这个差值小,那么说明A[i]小了,i++
附上Python版:
② 二分 (单独看二分部分是$O(log(n))$) —>因为sortB了还有遍历A所以是$O(n)$ =$O(max(m,log(n),n))$ (看这个排序是哪种了 不一定O(m),不过总时间复杂度肯定是O(n)因为遍历A了)
def fairCandySwap(self, A: List[int], B: List[int]) -> List[int]:
#sum_a = sum(A), sum_b = sum(B),sum_m = (sum_a + sum_b) // 2
n, m, sum_A, sum_总 = len(A), len(B), sum(A), (sum(A) + sum(B))//2
B.sort()
def binary_search(arr, target, l, r): #要搜的数列,要找的数,要搜的起点(左端点)),终点(右端点)
while l <= r:
m = (l + r) // 2
if arr[m] < target:
l = m + 1
elif arr[m] > target:
r = m - 1
else:
return m
return -1
for i in range(n):
tar = sum_总 - sum_A + A[i]
ind = binary_search(B, tar, 0, m-1)
if ind != -1:
return [A[i], B[ind]]
return []
③暴力:
def fairCandySwap(self, A: List[int], B: List[int]) -> List[int]:
df_x = (sum(A) - sum(B)) // 2
#ans = []
#Aset = set(A)
for item in B:
if item + df_x in A:
return [item +df_x, item] #可放进ans数组里显得正规一点,不过就是开了多点空间
#break
#return ans
加了二分以后变成400ms多了、for item这种暴力搜的效率还是八太行。暴力跑了3s