这是悦乐书的第 339 次更新, 第 363 篇原创
01 看题和准备
今天介绍的是 LeetCode 算法题中 Easy 级别的第 208 题 (顺位题号是 888).Alice 和 Bob 有不同大小的糖果棒: A[i] 是 Alice 拥有的第 i 个糖果棒的大小, B[j] 是 Bob 拥有的第 j 个糖果棒的大小.
由于他们是朋友, 他们想交换一个糖果, 以便交换后, 他们都有相同的糖果总量. (一个人拥有的糖果总量是他们拥有的糖果大小的总和.)
返回一个整数数组 ans, 其中 ans[0] 是 Alice 必须交换的糖果的大小, ans[1] 是 Bob 必须交换的糖果的大小.
如果有多个答案, 你可以返回其中任何一个. 答案保证存在. 例如:
输入: A = [1,1],B = [2,2]
输出:[1,2]
输入: A = [1,2],B = [2,3]
输出:[1,2] [2,3]
输入: A = [2],B = [1,3]
输出:[2,3]
输入: 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
保证 Alice 和 Bob 的糖果总量不同.
保证有答案.
本次解题使用的开发工具是 eclipse,jdk 使用的版本是 1.8, 环境是 win7 64 位系统, 使用 Java 语言编写和测试.
02 第一种解法
Alice 和 Bob 的糖果总量不一样, 要想答案肯定存在, 他们两人的糖果总量差值肯定为偶数, 只有差值为偶数时, 对差值进行平分得到一个平均值, 糖果总量多的一方减去平均值, 少的一方加上平均值, 此时两人的糖果总量是相等的.
因此, 我们只需要求出两人的糖果总量差值的平均数, 拿此平均数加上一方中的任意一个糖果的大小, 去匹配另外一方中的糖果大小, 能够匹配上, 说明这两个糖果是需要双方交换的, 在此情景下, 此题有点类似于 Two Sum.
- public int[] fairCandySwap(int[] A, int[] B) {
- int[] result = new int[2];
- // 存储 A 中的元素 (换成 B 也行)
- Set<Integer> set = new HashSet<Integer>();
- int sumA = 0;
- for (int a : A) {
- sumA += a;
- set.add(a);
- }
- int sumB = 0;
- for (int b : B) {
- sumB += b;
- }
- // 两人糖果总量之差的平均数
- int num = (sumA-sumB)/2;
- // 遍历 B 中元素, 加上差值平均数去另外一个数组里匹配,
- // 能匹配上, 表明遇到了需要交换的元素.
- for (int b : B) {
- if (set.contains(b+num)) {
- return new int[]{b+num, b};
- }
- }
- return result;
- }
03 第二种解法
针对第一种解法使用的 HashSet, 我们还可以换成另外的数据结构来代替, 使用一个 boolean 类型的数组来存储 A 中的值, 其他思路不变.
- public int[] fairCandySwap2(int[] A, int[] B) {
- int[] result = new int[2];
- boolean[] set = new boolean[100001];
- int sumA = 0;
- for (int a : A) {
- sumA += a;
- set[a] = true;
- }
- int sumB = 0;
- for (int b : B) {
- sumB += b;
- }
- int num = (sumA-sumB)/2;
- for (int b : B) {
- if (b+num> 0 && b+num < 100001 && set[b+num]) {
- return new int[]{b+num, b};
- }
- }
- return result;
- }
04 小结
算法专题目前已连续日更超过六个月, 算法题文章 208 + 篇, 公众号对话框回复 [数据结构与算法] ,[算法] ,[数据结构] 中的任一关键词, 获取系列文章合集.
以上就是全部内容, 如果大家有什么好的解法思路, 建议或者其他问题, 可以下方留言交流, 点赞, 留言, 转发就是对我最大的回报和支持!
来源: http://www.bubuko.com/infodetail-3077497.html